[백준 11726] 2*n 타일링

문제

접근

2*1 의 경우는 1가지

2*2의 경우는 2가지

2*3의 경우는 3가지

...

규칙이 있는 것을 찾아냈다.

예를 들어 n=5인 경우, 마지막 2*1 부분  빼고 모두 차있는 경우 + 마지막 2*2 부분이 가로로 채워져 있고 모두 차있는 경우

두 가지 경우를 더한 경우의 수가 모든 경우의 수이다.

점화식 : dp[i] = dp[i-1] + dp[i-2]

코드

import java.util.*;

public class Main {
    static int[] dp;
    static int N;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        dp = new int[N + 2];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i < N + 1; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
        }
        System.out.println(dp[N]);
    }
}