[Java] 백준 11726 - 2xn 타일링

Baekjoon_11726 - 2xn 타일링

https://www.acmicpc.net/problem/11726

문제

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

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

입력

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

출력

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

---

해결방법

• 세로 길이는 2로 고정되어 있으므로, 가로의 길이만 고려하면 된다.

• 가로를 길이가 1인 타일로 채울지 2인 타일로 채울지에 대한 문제로, 결국 n을 1, 2의 합으로 나타내는 가짓수를 구하는 것과 같다.

• 이 때 자료형의 범위에 주의해야 하는데, dp[n] = (getCnt(n-1) + getCnt(n-2)) 로 한다면 dp 배열값의 범위가 int를 넘어가게 되고, 심지어 long 범위까지 넘어가게 되버린다.

  따라서 굳이 더 큰 범위의 자료형을 찾기보다는 dp[n]에 값을 저장하는 계산 과정에서 10007으로 나눈 나머지를 저장하면 된다.

코드

package minsung.week11;

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

public class Baekjoon_11726 {
    static int[] dp = new int[1001];

    public static void main(String[] args) throws IOException {
        dp[1] = 1;
        dp[2] = 2;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        System.out.println(getCnt(n));

    }

    public static int getCnt(int n){
        if(dp[n] == 0){
            dp[n] = (getCnt(n-1) + getCnt(n-2)) % 10007;
        }

        return dp[n];
    }
}