처음으로 참가해본 코드포스 라운드다. 밤 11시 넘어서 시작하니 군대 안에 있을때는 참가하고 싶어도 할 수가 없었는데 말출 나와서 처음으로 참가해봤다.

시간을 잘 못 알아서 20분정도 늦게 시작했고 두 문제밖에 못 풀었다 ㅠㅠ. 조금 더 일찍 시작했으면 세문제 까지 풀 수 있었을것 같은데..

최근에 휴가를 많이 나오다보니 조금 나태해진것 같은데 이번에 라운드 참가하고나니 의욕이 다시 생겼다.

풀이

A. Buy A Shovel

http://codeforces.com/contest/732/problem/A

삽을 사야한다. 삽의 가격이 k원일때, 10원 동전이 무한개를 사용할 수 있고 r원 동전이 단 하나 있을때 거스름돈 없이 삽을 살 수 있는 최수 갯수를 구하는 문제이다. 약간 함정이 있는게 거스름돈 없이 사면 된다는 것이 함정이다. r원 동전이 하나밖에 없기 때문에 처음에 r원을 무조건 사용해야 한다는 생각을 했었는데 WA가 나와서 다시 보니 그냥 거스름돈을 남기지 않으면 되는거였다. 매우 쉬운 문제였다.

#include <stdio.h>
int main(){
	int k,r,m=1;
	scanf("%d%d",&k,&r);
	while(1){
		int price = k*m;
		if(price % 10 == 0 || price % 10 == r)
			break;
		m++;
	}
	printf("%d",m);
}

B. Cormen — The Best Friend Of a Man

http://codeforces.com/contest/732/problem/B

개를 산책시키기 위한 계획을 짜야한다. n일동안의 계획이 주어졌을때 강아지를 이틀 연속으로 최소 k번 산책을 시켜야 한다. 첫번째 예제를 보면 n=3, k=5이고 1일부터 3일까지 각각 {2, 0, 1}번 산책을 하려고 하는데 이 계획은 이틀 연속으로 최소 5번 산책을 시키지 않으므로 산책을 더 시켜야한다.여기서 보면 알겠지만 이 문제는 스페셜 저지 문제이다. 연속되는 이틀간 최소 5번 산책을 시키려면 4번 더 산책을 가야하는데 이 때 {2, 3, 2}와 {2, 4, 1} 둘 다 답이 되므로 아무거나 출력해도 된다.

처음에는 DP처럼 보여서 DP로 풀었는데 메모이제이션이 제대로 안된다. 산책시킬 최소 횟수의 최대값은 n*k/2이기때문에 메모이제이션을 적용하려면 메모리가 부족할것이다. 그래서 다시 생각해보니 값이 범위가 생각보다 작으므로 그냥 풀어도 될것 같다는 생각이 들어서 연속되는 이틀을 모두 비교하면서 만약 k번 산책을 시키지 못한다면 더 산책을 시켜야 할 만큼 늦게 오는 날에 더 산책을 시키는 방식으로 코드를 작성했다.

#include <stdio.h>
int walk[501], n, k;
int main() {
	int i, count = 0;
	scanf("%d%d", &n, &k);
	for (i = 1; i <= n; i++)
		scanf("%d", &walk[i]);
	for (i = 2; i <= n; i++) {
		if (walk[i - 1] + walk[i] < k) {
			count += k - (walk[i - 1] + walk[i]);
			walk[i] += k - (walk[i - 1] + walk[i]);
		}
	}
	printf("%d\n", count);
	for (i = 1; i <= n; i++)printf("%d ", walk[i]);
}

C. Sanatorium

http://codeforces.com/contest/732/problem/C

이 문제는 못 풀었는데, 라운드가 거의 종료되었을때 감을 잡아서.. 나중에 다시 한번 풀어봐야겠다.

문제

https://algospot.com/judge/problem/read/BOGGLE

풀이

동적 계획법 문제같아서 동적 계획법으로 풀었다. 그래프로 풀 수 있지 않을까라는 생각이 들지만 나는 DP로만 풀었으므로 DP 풀이만 적음.

먼저 findAll()과 solve() 두개의 함수를 작성했다. findAll()은 좌표 [0,0]부터 [4,4]까지, 즉 모든 칸에서 입력받은 문자열을 찾을 수 있는지 확인하는 solve()를 실행시키는 함수이다.

solve함수는 세개의 인자를 받는데 각각 게임판의 y좌표, x좌표, 게임판의 y,x 좌표의 문자열과 비교할 찾을 문자열의 index번째 문자다.

메모이제이션은 dp[y][x][index] = 게임판[y][x] 좌표에서 시작해 word[index] 이후의 문자들을 매칭 시킬수 있는가에 대해 메모이제이션을 적용했다. 입력값이 작아서 최대 250크기 만큼의 배열만 사용하므로 3차원 배열을 사용해도 문제가 없었다.

#include <cstdio>
#include <cstring>
char map[5][6],word[11];
int dp[5][5][10];
int solve(int y, int x, int index){
	int i,j;
	//메모이제이션 값 체크. 초기값 -1이 아니라면 바로 리턴
	int& ret = dp[y][x][index];
	if(ret != -1) return ret;
	for(i=-1;i<=1;i++){
		for(j=-1;j<=1;j++){
			//인접한 칸을 검사하며 게임판을 벗어났다면 패스한다.
			if((i==0&&j==0)||y+i<0||y+i>4||x+j<0||x+j>4) continue;

			//매칭되는 문자열을 찾았을때
			if(map[y+i][x+j] == word[index]){
				//다음 문자가 null이라면 즉, 모든 문자를 다 찾았다면 true를 반환한다.
				if(word[index+1] == '\0') return ret = 1;
				//아직 다 찾지 못했으므로 현재 위치에서 시작하는 다음 문자를 찾는 함수를 재귀 호출한다.
				ret = solve(y+i,x+j,index+1);
				//만약 현재 위치에서 문자열 매칭에 성공했다면 더 찾을 필요가 없으므로 바로 1를 반환한다.
				if(ret==1) return ret;
			}
		}			
	}
	//여기까지 왔다면 문자를 찾지 못한것이므로 0을 반환한다.
	return ret = 0;
}
int findAll(){
	int i,j;
	for(i=0;i<5;i++){
		for(j=0;j<5;j++){
			int& ret = dp[i][j][0];
			if(ret != -1) return ret;
			if(map[i][j] == word[0]){
				ret = solve(i,j,1);
				if(ret) return ret;
			}
		}
	}
	return 0;
}
int main(){
	int i,j,t,n;
	scanf("%d",&t);
	while(t--){
		for(i=0;i<5;i++)
			scanf(" %s",map[i]);
		scanf(" %d",&n);
		while(n--){
			memset(dp,-1,sizeof(int)*250);
			scanf(" %s",word);
			printf("%s %s\n",word,findAll()?"YES":"NO");
		}
	}
}

문제

https://algospot.com/judge/problem/read/SNAIL

풀이

완전 탐색 코드를 먼저 만들었다. 비가 올 확률이 75%이고 비가 올때는 2m, 비가 오지 않을 확률이 25%이고 비가 오지 않을때는 1m씩 올라가므로 그냥 재귀적으로 함수를 호출해주며 m일이 지났을때 우물을 다 올라갔는지 확인해주는 코드를 작성했다.

#include <cstdio>
int n,m;
double solve(int cur, int day){
	if(day == m) return cur >= n;
	return (0.25*solve(cur+1,day+1)) + (0.75*solve(cur+2,day+1));
}
int main() {
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		printf("%.10lf\n",solve(0,0));
	}
}

잘 작동하지만 완전 탐색인만큼 큰 입력이 들어오면 엄청 오래 걸린다. 그러므로 메모이제이션을 적용해서 중복 계산을 하지 않도록 코드를 바꿔줘야 한다. dp[height][day] = day일째에 height만큼 올라 왔을때 우물 끝까지 올라갈 확률이라 하고 메모이제이션을 적용했다.

또한 아래와 같은 부분에 대해 고민을 하며 코드를 작성했다.

• double은 -1로 memset이 안되는거 같다. > 그래서 직접 for문으로 값을 초기화시켰다.
• 올라갈 수 있는 최대 높이는 N이 아니다. > N-1에서 비가 와 N+1까지 올라갈 수 있는 경우가 있으므로 배열 크기를 1 더 잡아줘야 한다.

#include <cstdio>
int n,m;
double dp[1003][1001];
double solve(int cur, int day){
	if(day == m) return cur >= n;
	if(cur >= n) return 1.;
	double& ret = dp[cur][day];
	if(ret != -1.)	return ret;
	return ret = (0.25*solve(cur+1,day+1)) + (0.75*solve(cur+2,day+1));
}
int main() {
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		for(int i=0;i<=1002;i++)
			for(int j=0;j<=1000;j++)
				dp[i][j] = -1.0;
		printf("%.10lf\n",solve(0,0));
	}
}

문제

https://algospot.com/judge/problem/read/ZEROONE

풀이

그냥 문제대로 구현하면 푸는 문제인줄 알고 풀었다가 엄청 많이 틀렸다. 문자열의 최대 길이가 L이라했을때 별 다른 방법 없이 코드를 작성하면 전체 수행시간이 $O(NL)$이라 시간 초과가 나게 된다. 그러므로 수행 시간의 상한을 $O(N * lg(L))$ 정도라 생각하고 풀어야 한다.

수열의 값은 0과 1밖에 없고 최대값과 최소값이 같다는 뜻은 해당 구간 i,j의 모든 원소가 같다는 뜻이므로 구간마다 그룹을 나누어 배열에 저장하면 전체 수행 시간을 $O(N)$으로 줄일 수 있다.

예를들어 수열 000110010가 있다 할때 그룹화하여 000112234로 저장한뒤 그룹 배열의 i와 j번째 값이 같은지만 비교해주면 되기 때문이다.

#include <stdio.h>
int main() {
	int t,i,j,tmp;
	int diff[1000001]={0};
	char s[1000001];
	scanf("%s",s);
	for(i=1;s[i]!='\0';i++){
		diff[i] = diff[i-1];
		if(s[i-1] != s[i]) diff[i]++;
	}
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&i,&j);
		printf("%s\n",diff[i] == diff[j]?"Yes":"No");
	}
	return 0;
}

문제

https://algospot.com/judge/problem/read/JLIS

풀이

이 문제를 완전 처음에.. 그러니까 동적계획법이 뭔지도 모르고 접했을때는 그냥 두 수열을 중복되는 수 없이 한 수열로 합친 다음에 합친 수열의 길이를 출력하게 했다. 놀랍게도 이 방식이 예제 입력에 대해서는 제대로 된 답을 출력해주기 때문에 코드를 제출했으나 당연히 WA를 받았다.

그리고 몇 일 전에 LIS 문제를 해결한 뒤 이 문제를 다시 접했는데 이 때는 LIS와 비슷하게 해결하면 될 줄 알았다. 두 수열의 LIS를 각각 구한뒤 각 수열의 길이를 출력하는 방법을 생각해보았으나 세 번째 예제인 $A=\{10, 20, 30\}, B=\{10, 20, 30, 1, 2\}$같은 경우에서는 A,B 수열 모두 $\{10, 20, 30\}$가 LIS이므로 6을 반환하지만 실제로는 $A=\{10, 20, 30\}, B=\{1, 2\}$인 5가 답이다.

LIS 문제는 한 개의 수열에 대한 인덱스 값을 인수로 받는 solve(int)를 작성했었는데 이 문제도 비슷하게 두개의 수열의 인덱스 값을 각각 받는 solve(int, int)를 작성하면 될 것 같았다. 문제를 해결하는 코드를 작성하면서 아래와 같은 부분에 대해 유의하며 작성했다.

• 모든 원소의 값은 signed integer 범위에 들어간다. 즉, 최소값은 INT_MIN이다.
• 한 수열의 원소를 아무것도 선택하지 않는 상태가 있을 수 있다.

#include <cstdio>
#include <cstring>
#include <climits>
int n,m,A[100],B[100],dp[101][101];
int max(int a, int b){return a>b?a:b;}
int solve(int Ai, int Bi){
	int &ret = dp[Ai+1][Bi+1];
	if(ret != -1) return ret;
	ret = 0;
	int pA, pB, pivot;
	pA = Ai == -1 ? INT_MIN : A[Ai];
	pB = Bi == -1 ? INT_MIN : B[Bi];
	pivot = max(pA,pB);
	for(int i=Ai+1;i<n;i++)
		if(pivot < A[i])
			ret = max(ret, solve(i,Bi)+1);
	for(int i=Bi+1;i<m;i++)
		if(pivot < B[i])
			ret = max(ret, solve(Ai,i)+1);
	return ret;
}
int main() {
	int t;
	scanf("%d",&t);
	while(t--){
		int i;
		memset(A,0,sizeof(A));
		memset(B,0,sizeof(B));
		memset(dp,-1,sizeof(int)*101*101);
		scanf("%d%d",&n,&m);
		for(i=0;i<n;i++)
			scanf("%d",&A[i]);
		for(i=0;i<m;i++)
			scanf("%d",&B[i]); 
		printf("%d\n",solve(-1,-1));
	}
}