백준 01타일 - DP

문제 설명

문제는 00 타일과 1타일을 사용하여 만들 수 있는 길이 N의 2진수의 개수를 구하는 문제이다.
단순 0 1 DFS를 통하면 2^100만이고, 결과값을 15746으로 나눈 나머지이므로 DP 문제이다.

DP 풀이

DP 풀이의 순서는 아래처럼 풀면 된다.

1. DP 점화식 구하기
2. DP 초깃값 설정
3. N이 작을때 예외 케이스 설정하기

점화식 구하기

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

}