백준 Java 11726_2 x n 타일링

• n-1의 타일에 세로타일이 하나 추가되고
• n-2의 타일에 가로타일디 두개 추가된 형태를 가지고 있다.
• 따라서, dp[n]=dp[n−1]+dp[n−2]라는 점화식을 갖게 된다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int k = Integer.parseInt(br.readLine());

        int[] dp = new int[1001];
        dp[1]=1;
        dp[2]=2;
        for (int i = 3; i <= k; i++) {
            dp[i] =(dp[i-1] + dp[i-2]) % 10007;
        }
        System.out.println(dp[k]);

    }
}