kingsubin

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

// # 2xn 타일링
public class boj_11726 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[] dp = new int[1001];

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        dp[1] = 1; dp[2] = 2;

        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i-1] + dp[i-2]) % 10007;
        }

        System.out.println(dp[n]);
    }
}

 

- dp 문제의 경우 점화식을 생각하는게 중요한데 점화식을 떠올리기가 어렵다 ...

 

- 경우의 수를 쪼갠다

- 마지막 부분에 블록을 채우는 방법은 세로막대 하나일경우, 가로막대 두개일경우 이렇게 2가지밖에 없다.

- 세로막대 한 개인 경우는 dp[n-1], 가로막대 두 개인 경우는 dp[n-2]

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