[백준11726번] 2xn타일링 - java

문제

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

###입력

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

출력

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

예제 입력 1

2

예제 출력 1

2

예제 입력 2

9

예제 출력 2

55

나의 풀이

아래 그림과 같이 타일을 그려보고 개수를 세어보니 피보나치와 같이 앞의 두개의 개수를 더한 개수였다.

그러나 처음에 dp에는 모두 그 원래 개수를 저장하고 마지막에 출력을 할때 10007로 나눈 나머지를 출력하였지만 틀리 값이 나왔었다. 그래서 dp에 저장할때마다 10007로 나눈 나머지를 저장하니 문제를 해결할 수 있었다.

코드

import java.util.Scanner;
/**
 * 11726번 2xn타일링
 */

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

        int dp[] = new int[n+1];

        for (int i=1; i<=n; i++) {
            if (i==1) dp[i] = 1;
            else if (i==2) dp[i] = 2;
            else dp[i] = (dp[i-2] + dp[i-1]) % 10007 ;
        }

        System.out.println(dp[n]);
    }
}