끼룽의 블로그

문제 링크

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]);
	}

}