11726번(2xn 타일링)

첫 시도

• N이 1000 = 10^3
• dp를 사용하면 O(N)으로 해결 가능
• N이 커져도 결국 어떤 패턴이 반복됨
• dp[i] = dp[i-2] + dp[i-1];

해결

• 10007으로 나눈 나머지를 dp배열에 저장했어야했는데 조건을 제대로 확인하지 않아 한참 헤맸다.
• 조건을 잘 확인하자

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N+1];
        if(N == 1){
            System.out.println(1);
            return;
        }
        dp[1] = 1;
        dp[2] = 2;

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

    }
}

참고

• 직접구현