[BOJ] 백준 11727 2×n 타일링 2

출처: https://www.acmicpc.net/problem/11727

 Input 
12

 Output 

2731

2 * N 직사각형이 주어질 때, 2×1과 2×2 타일로 채우는 방법의 수

 

첫번째 줄에 N을 입력 받습니다.

▶ 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력

 

Dynamic Programming (DP) 이용.

- 자세한 풀이는 [BOJ] 1793 타일링 참고

[BOJ] 백준 1793 타일링

※ 1 ≤ N ≤ 1000 이기 때문에 DP[0] 고려 X

* 테스트 Case 중에 DP[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));
         
        int N = Integer.parseInt(br.readLine());
        int DP[] = new int[N+1];
        // 문제 조건 1 <= N <= 1000
        DP[1]=1;
         
        if(N >= 2) DP[2]=3;
         
        for (int i = 3; i <= N; i++) {
            DP[i]=(DP[i-1] + DP[i-2]*2) % 10007;
        }
         
        System.out.println(DP[N]);
    }
}