(11726) 2*n 거리

문제

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

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

입력

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

출력

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

---

문제 풀이

해당 문제는 DP 알고리즘으로 해결 할 수 있는 문제이다. 길이가 1인 타일을 채우는 방법은 1가지, 길이가 2인 타일을 채우는 방법은 2가지, 길이가 3인 타일을 채우는 방법은 3가지로 i = (i -1) + (i - 2) 이라는 규칙이 생긴다. 이것을 코드로 적어내면 되는 문제이다.

 

---

나의 답안

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2; i<=n; i++) {
            dp[i] = (dp[i-1] + dp[i-2]) % 10007;
        }
        System.out.println(dp[n]);
    }
}