[백준/Java] 11726번: 2 x n 타일링

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

11726번: 2×n 타일링

다이나믹 프로그래밍 문제이며, 이 유형의 문제를 해결하기 위해선 점화식을 잘 세워야 한다.
이 문제에서는 항상 세로의 길이가 2로 고정되어 있으므로, 가로의 길이가 1씩 늘어남에 따른 경우의 수의 증가에 주목하면 된다.

각 경우마다 가능한 타일링의 수를 직접 구하다 보니 규칙이 보였다.
dp[2]=2, dp[3]=3, dp[4]=5, dp[5]=8... 

블록은 가로로만 증가하기 때문에 n개의 타일링은 n보다 작은 부분 문제로 나누어 정의할 수 있었고, 규칙상 점화식은 다음과 같다.

dp[n]=dp[n−1]+dp[n−2]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Scanner;

public class Main {
    static int N;
    static int[] D;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        D = new int[1001];
        D[1] = 1;
        D[2] = 2;

        for(int i=3; i<=N; i++) {
            D[i] = D[i-1] + D[i-2];
            D[i] %= 10007;
        }
        System.out.println(D[N]);

    }
}