끼룽의 블로그

문제 링크

https://www.acmicpc.net/problem/1904

문제 해설

점화식을 유도해내야 하는 문제이다.
타일을 '00', 혹은 '1' 로만 붙일 수 있다.
즉, 타일을 2개 붙이는 경우와 1개 붙이는 경우가 있기 때문에, n번째 답을 구하기 위해선 n-1번째와 n-2번째 경우를 탐색해야 한다.

1) 'n - 1'번째 경우와 'n'번째 경우의 관계

만약 'n-1'개의 타일을 모든 경우의 수로 놓았다고 가정해보자.
그렇다면, 타일을 1개만 추가할 수 있으므로 '1'타일을 추가하는 경우밖에 없다.
따라서, 'dp[n] = dp[n - 1]'이 된다.
 *dp[n] = n개의 타일을 놓을 수 있는 모든 경우의 수

*만약 'n-1'번째 타일이 '0'타일 홀수개로 끝난다면, 'n'번째에 '0'타일 한개를 놓을 수 있다고 생각할 수 있다.
하지만, 'n-1'번째 타일을 모든 경우의 수로 놓았다는 전제 조건이 있기 때문에,
'n-1'번째 경우에는 '0'타일이 홀수개로 끝나는 경우가 없으므로 고려하지 않아도 된다.

2) 'n - 2'번째 경우와 'n'번째 경우의 관계

만약 'n-2'개의 타일을 모든 경우의 수로 놓았다고 가정해보자.
이때, 타일을 2개 추가할 수 있으므로 '00'타일을 추가하거나, '11'타일을 추가할 수 있다.
하지만, '11'타일을 놓는 경우는 'n-1'번째 경우와 중복이 되므로 제외해야 한다.
따라서, 'dp[n] = dp[n - 2]'가 된다.

위 두 가지 경우를 합하면, dp[n] = dp[n - 1] + dp[n - 2]가 된다.
이때, 정답을 15746로 나눈 값을 출력하라는 조건이 있는데, 나머지 연산은 분배법칙이 적용되므로,
(dp[n - 1] + dp[n - 2]) % 15746 = {(dp[n - 1] % 15746) + (dp[n - 2] % 15746)} % 15746 이 성립한다.

답안

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		//Input
		int n = scanner.nextInt();
		
		int[] dp = new int[n + 1];
		
		//Catch array index out of bounds
		if(n == 1) {
			System.out.println(1);
			return;
		}
		if(n == 2) {
			System.out.println(2);
			return;
		}

		//Initial condition
		dp[1] = 1;
		dp[2] = 2;
		
		//Recurrence relation
		for(int i = 3; i <= n; i++) {
			dp[i] = dp[i - 2] + dp[i - 1];
			dp[i] %= 15746;
		}
		
		//Output
		System.out.println(dp[n]);
	}

}

문제 링크

https://www.acmicpc.net/problem/9184

문제 해설

메모이제이션(memoization) 만으로 풀 수 있는 문제.
이미 구해놓은 값을 배열에 저장해 놓고, 만약 저장되어 있는 값을 불러오는 경우라면 빼서 쓰도록 하면 된다.

답안

import java.util.Scanner;

public class Main {
	
	static int[][][] dp_arr = new int[21][21][21];
	
	public static int w(int a, int b, int c) {
		//BC
		if(a<=0 || b<=0 || c<=0) {
			return 1;
		}
		if(a>20 || b>20 || c>20) {
			return w(20, 20, 20);
		}

		//Memoization
		if(dp_arr[a][b][c] != 0) {
			return dp_arr[a][b][c];
		}
		
		//Condition1
		if(a<b && b<c) {
			dp_arr[a][b][c] =  w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
			return dp_arr[a][b][c];
		}
		
		//Condition2(otherwize)
		dp_arr[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1);
		return dp_arr[a][b][c];
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int a = 0;
		int b = 0;
		int c = 0;
		
		while(true) {
			//Inputs
			a = scanner.nextInt();
			b = scanner.nextInt();
			c = scanner.nextInt();
			
			//Break condition
			if(a==-1 && b==-1 && c==-1) {
				break;
			}
			
			//Outputs
			System.out.printf("w(%d, %d, %d) = %d\n", a, b, c, w(a, b, c));
		}
		
		scanner.close();
	}
}