백준 11726번 2 x n 타일링 (자바) - DP

2×n 타일링 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

83129

30992

22585

35.015%

문제

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

---

풀이 : 세로의 길이가 항상 2이므로 가로만 고려해도 된다. 따라서 가로를 1과 2만을 이용하여 어떻게 자를지 생각하여 풀면 된다. 즉, 이 문제는 n을 1과 2의 합으로 나타내는 방법의 수를 구하는 문제와 동일하다. 

예를 들어, 2 = (1+1) (2) 이고, 3 = (1+1+1) (1+2) (2+1) , 4 = (1+1+1+1) (1+1+2) (1+2+1) (2+1+1) (2+2) 이다. 

이 때 4의 모든 경우의 수는 2의 모든 경우의 수에 2를 더한 것과 3의 모든 경우의 수에 1을 더한 것과 같다.

즉, n 번째 수의 방법의 수는 n-1과 n-2의 방법의 수를 더하면 된다.

---

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Test {

    static int n;
    static int[] dp;
    public static void main(String args[]) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dp = new int[n + 1];
        System.out.println(countFunction(n));
    }

    static int countFunction(int n) {
        if (n == 1) return 1;  //이거 해주지 않으면 arrayIndexOutOfBounds 에러
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        if(dp[n] > 0) return dp[n];
        if(n > 2) {
            dp[n] = (countFunction(n - 1) + countFunction(n - 2)) % 10007;
            /*여기서 10007을 나눠주지 않으면 n이 일정 숫자 이상일 때 int 배열이 저장할 수 있는
            범위를 벗어나 이상한 값이 나옴*/
        }
        return dp[n];
    }
}

주의해야 할 점은 dp라는 배열의 크기를 n+1개로 하였기 때문에 n이 1인 경우 배열의 크기는 2가 되어 dp[2] = 2를 수행할 때 ArrayIndexOutOfBounds 에러가 뜨게 된다. 따라서 n이 1인 경우는 함수를 수행하지 않고 1을 return 하도록 했다. 

또, 문제에서 10007로 나눈 나머지 값을 출력하도록 했는데 모든 함수의 계산이 끝난 후 10007을 나눠주면 틀린 값이 출력된다. 왜냐하면 n이 1000까지 입력될 수 있어서 어느 순간 dp[n]에 int형의 범위를 넘어서는 수가 들어가야 하는 경우가 발생하고, 이 때 잘못된 값이 dp[n]에 들어가게 되기 때문이다. 따라서 dp[n]에 값을 넣어주기 전에 10007을 나누어서 나머지를 배열에 저장하도록 해야한다.