문제는 00 타일과 1타일을 사용하여 만들 수 있는 길이 N의 2진수의 개수를 구하는 문제이다.
단순 0 1 DFS를 통하면 2^100만이고, 결과값을 15746으로 나눈 나머지이므로 DP 문제이다.
DP 풀이의 순서는 아래처럼 풀면 된다.
dp[i] = cnt // 길이가 i인 타일의 경우의 수 cnt개
dp[i] = dp[i-1] + 2*dp[i-2] // i-1길이에 "1"타일을 맨 뒤에 추가, i-2길에 "00", "11" 타일을 맨 뒤에 추가
먼저 생각한 것은 가장 뒤에 타일을 추가하는 방식이다.
길이 1 : 1
길이 2 : 11 00
길이 3 : 111 001 100 111 (중복발생)
길이 2를 뒤에 붙일때 "11" "00"을 추가할 수 있으니까 *2를 해서 추가했지만 실제로는 "11"을 추가할 경우 중복이 발생하므로 "11"을 추가하면 안된다.
즉 점화식 이거다.
dp[i] = dp[i-1] + dp[i-2]
import java.util.*;
public class Main {
public static void main(String[] args) {
// 여기에 코드를 작성해주세요.
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.nextLine());
int[] dp = new int[n+3];
dp[1]= 1;
dp[2] = 2;
for(int i=3;i<=n;i++){
dp[i] = (dp[i-2]%15746+dp[i-1]%15746)%15746;
}
System.out.print(dp[n]%15746);
}
}