[백준]#11727 2xn 타일링 2

문제

2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

2

예제 출력 1

3

예제 입력 2

8

예제 출력 2

171

예제 입력 3

12

예제 출력 3

2731

풀이

이 문제는 DP(다이나믹 프로그래밍) 문제로 점화식을 세워서 풀면 쉽게 풀 수 있다. 점화식은 an = a(n-1)+2*a_(n-2) 으로 풀었다.

import java.util.Scanner;

public class Main {
    static int cnt = 1;
    static int an = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        if(N==1)
            System.out.println(1);

        else {
            DP(1, 1, N);
            System.out.println(an);
        }
    }

    public static void DP(int a0, int a1, int n) {
        if(cnt==n)
            return ;
        else {
            an = (a1 + 2*a0)%10007;
            cnt++;
            DP(a1, an, n);
        }
    }
}