[알고리즘] 백준 11727_2xn 타일링 2

백준_11727

• dp 문제
• 일단 적다가 갑자기 번뜩
• 역시 dp문제는 규칙 보일때까지 적어야되나보다

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int MOD = 10007;
        if(N == 1) {
            System.out.println(1);
            return;
        } 
        if (N==2) {
            System.out.println(3);
            return;
        } 
        int[] dp = new int[N+1];
        dp[1] = 1;
        dp[2] = 3;
        for (int i = 3;i <=N; i++) {
            dp[i] = (dp[i-1]+dp[i-2]*2)% MOD;
        }
        System.out.println(dp[N]);
        
    }
}