<BOJ>11726번: 2xn 타일링

문제

11726번: 2xn 타일링

접근

• 1x2, 2x1 타일로 직사각형을 직접 채워보면 일정한 패턴이 반복된다.
• 결론적으로 피보나치 수열과 같은 꼴의 점화식을 도출하게 된다.

내 코드

import java.io.*;

public class Main {
    static int[] dp = new int[1001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        dp[1] = 1; dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i-2] + dp[i-1]) % 10007;
        }
        System.out.println(dp[n]);
    }
}