[백준] 11727 2Xn 타일링2 - 자바(Java)

11727번

2Xn 타일링2

 

 

 

문제

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

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

 

입력

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

 

출력

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

 

 

 

 

 

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

11727번: 2×n 타일링 2

---

1. 작은 문제의 답을 구하여 규칙을 구한다

 

dp[1] = 1

dp[2] = 3

dp[3] = 5

dp[4] = 11

dp[5] = 21

...

 

dp[n] = dp[n-1] + dp[n-2]*2 라는 식이 나온다.

 

 

 

이를 재귀함수를 이용한 Top-down 방식을 이용하여 나타내면,

import java.util.*;

public class B11727 {
    static Integer[] dp;

    public static void main(String[] arg) {
        Scanner input = new Scanner(System.in);

        int n = input.nextInt();
        dp = new Integer[n + 1];
        dp[0] = 0;

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

    }

    public static int count(int n) {
        if (n == 2) {
            dp[n] = 3;
        }
        else if (n == 1) {
            dp[n] = 1;
        }
        else if (dp[n] == null) {
            dp[n] = ((count(n-2))*2 + count(n-1))%10007;
        }
        return dp[n];
    }
}

와 같다.

 

 

 

 

tip) 10,007을 매번 나누어주지 않으면 오버플로우가 발생하여 값이 달라지게 된다.

tip) nullpointer 오류가 나지 않도록 dp의 0, 1, 2 등의 값을 초기화 해주어야 한다.