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

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

11727번: 2×n 타일링 2

11726 문제를 이해하고 풀었다면 쉽게 풀리는 문제이다. 아래 블로그 참고

https://iyk2h.tistory.com/306

 

기존 문제에서 2 * 2 정사각형 타일이 추가되었다.

위 그림과 같이 직사각형을 채워나갈 수 있게 된다.

n의 값이 3, 4일 때부터 규칙이 보이기 시작한다.

 

n = 3 일 때

색으로 구별해 두었는데,

빨간색은 박스는 n = 2 일 때 타일을 채우는 방법에 2 * 1 세로 타일을 추가했고, 오른쪽 박스는 n = 1 일 때 직사각형을 채우는 방법에 1 * 2 가로 2개의 타일과 2 * 2 정사각형 타일을 채웠다. ( 2 * 1 세로 타일은 이미 왼쪽박스에서 다 넣었기 때문)

 

n = 4 일 때

마찬가지로 색으로 구별해 두었는데,

n = 3 일 때 채우는 방법에 2 * 1 세로 타일 1개 추가 + n = 3 일 때 채우는 방법에 1 * 2 가로 타일 2개, 2 * 2 정사각형 타일 추가가 되었다.

 

2 * n 크기의 직사각형을 2*1 타일, 1*2 타일, 2*2 타일로 채우는 방법의 수를 countTile( n )이라고 할 때 규칙성을 통해 아래와 같은 식이 나오게 된다.

countTile( n ) = countTile( n - 1) + countTile( n - 2) * 2

 

여기서 ' countTile( n ) * 2 '를 한 이유는 가로길이가 2인 값에 들어갈 수 있는 방법은 타일은 1 * 2 가로 타일 2개와 2 * 2 정사각형 타일 1개 총 2가지 방법이 있기 때문이다.

 

자바 코드

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int input = Integer.parseInt(bf.readLine());

        /*
        규칙성 : dp[n] = dp[n-1] + dp[n-2] * 2;
        */

        int[] dp = new int[input + 1];

        dp[0] = 1;
        dp[1] = 1;

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

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