[백준] 11726 2×n 타일링 Java

문제

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

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

 

입력

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

 

출력

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

 

n이 5인 경우까지 경우의 수를 모두 찾아보았다.

n=4일 때 2, 3의 합계만큼, n=5일 때 3, 4의 합계만큼 경우의 수가 나오는 것을 확인할 수 있었다.

dp[i] = dp[i-1] + dp[i-2]의 공식을 가지고 코드를 작성했다.

 

코드

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int n;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        dp = new int[1001];
        dp[1] = 1;
        dp[2] = 2;

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

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

주의할 점은 dp 배열에 모두 저장하고 결과 출력할 때만 10007를 나누면 오류가 난다. 계산해야 하는 값이 너무 커서 생기는 일이라고 하니 저장할 때부터 10007를 나누어 주어야 한다.

그리고 처음에 dp를 선언할 때 new int[n+1]로 선언했는데 이렇게 선언하면 런타임에러(ArrayIndexOutOfBounds)가 발생한다.

n=1이 입력된 경우를 생각하면 왜 이런 오류가 발생했는지 쉽게 알 수 있었다.

그래서 1001로 설정해주니 해결됐다.

 

문제 출처

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