[백준] 타일 채우기 - Java

문제 출처

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

문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

예제 입력 1

2

예제 출력 1

3

힌트

아래 그림은 3×12 벽을 타일로 채운 예시이다.

풀이 방법

• 보자마자 DP 겠구나 싶었다...
• 문제 자체는 간단한 문제이나, 그 안의 점화식을 세우는게 좀 어려워서 노가다를 통해 풀었다...

• 3x2의 경우, 저렇게 기본형 3가지로 경우의 수가 존재한다

• 3x4 배치의 경우 각각 왼쪽, 오른쪽 면에 3x2 경우의 수의 배치를 할 수 있다 (3 x 3 = 9)
• 또 그림과 같이, 가운데 경계선에 가로 블럭을 배치하여 추가적인 조합을 만들 수 있다. (2가지)
• 총 11가지

점화식 발견!
-> 3x6에서는 또 3x4 배치를 3가지 쓸 수 있을 것이고... (11 x 3)
-> 그 이후에 나오는 (경계선에서) 추가적인 배치를 두번 할 수 있을 것이고... (3 x 2)
-> 3x6에서만 나올 수 있는 배치를 위 아래로 추가로 넣을 수 있을 것이다! (2가지)
이를 이를 식으로 표현하면, 아래와 같은 점화식이 나온다.
f(n) = 3 * f( n - 2 ) + 2 * f( n - 4 ) + 2 * f( n - 6 ) + ... + 2 * f(0)

• 해당 점화식을 발견했으면 바로 코드로 옮기면 끝이다.

풀이 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        // 홀수는 배치 불가
        if (N % 2 == 1) {
            System.out.println(0);
        } else {
            int[] dp = new int[N + 1];
            dp[0] = 1;
            dp[2] = 3;

            if (N == 2) {
                System.out.println(3);
            } else {
                for (int i = 4; i <= N; i++) {
                    dp[i] = dp[i - 2] * 3;
                    for (int j = i - 4; j >= 0; j -= 2) {
                        dp[i] += (dp[j] * 2);
                    }
                }

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

}

결과

회고

• 저번에 풀었던건데 또 점화식 세우거 까먹어서 오래걸렸다.