[백준 2133] 타일 채우기(Java)

문제 링크 : https://www.acmicpc.net/problem/2133

이 문제는 dp 문제입니다. dp 문제이니만큼 문제에서 요구하는 점화식을 잘 세우면 쉽게 풀 수 있습니다.

우선 홀수 개수일 경우에는 타일을 전부 채울 수 없기 때문에 0의 경우의 수를 가집니다. 그렇다면 짝수 개수를 알아보아야 할텐데, 먼저 2개일 때 가능한 경우의 수를 살펴보면

1. 맨 아래에 가로 블록이 있는 경우
2. 맨 위에 가로 블록이 있는 경우
3. 모두 가로 블록이 있는 경우

로 3가지입니다. 그렇다면 4개일 때는 가능한 경우의 수가 어떻게 될까요? 우선 기존 2개일 때의 경우의 수에서 3만큼 곱한, 즉 새롭게 2칸의 블록을 채우는 경우의 수가 있겠습니다. 하지만 여기서 끝이 아닙니다. 맨 아래에 모두 가로 블록이 있는 경우, 맨 위에 모두 가로 블록이 있는 경우 총 2가지의 경우의 수가 추가됩니다. 따라서 4칸일 경우 다음의 점화식을 얻을 수 있습니다.

dp[4] = dp[2]*3 + 2;

그렇다면 6개일 때는 어떨까요? 우선 기존 4개일 떄의 경우의 수에서 3만큼 곱한 경우의 수가 존재하며, 맨 아래와 맨 위에 모두 가로 블록이 있는 2개의 경우의 수도 존재합니다. 하지만 여기서 한 가지 더 있습니다. 바로 이전 단계, 즉 4개를 채우는 경우의 수 중 맨 아래와 맨 위를 모두 가로 블록으로 채우는 2가지의 특수 경우의 수일 경우 칸을 채우는 방법이 남아있는데, 이 부분은 해당 범위를 뺀 나머지, 즉 2칸을 채우는 경우의 수를 제일 왼쪽과 제일 오른쪽 2번을 곱한 값을 추가해주면 됩니다. 그렇다면 점화식은 다음과 같습니다.

dp[6] = dp[4]3 + 2 + dp[2]2

그렇다면 8개 이상일 때, 즉 n일 때는 어떨까요? 기존 경우의 수에서 3만큼 곱한 경우의 수와, 맨 아래, 맨 위 모두 가로 블록이 있는 2가지 경우까지는 똑같습니다. 하지만 특수 경우의 수가 2칸에서부터 n-4 칸까지 양 끝을 채우는 경우의 수도 지속적으로 더해주어야 합니다. 따라서 최종 점화식은 다음과 같습니다.

dp[n] = dp[n-2]3 + 2 + (dp[2]2 + dp[4]2 + ... + dp[n-4]2)

다음은 코드입니다.

import java.util.*;
import java.io.*;

public class Main{

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());

        int[] res= new int[31];

        // N이 홀수일 경우 완벽하게 채울 수 있는 경우의 수 없으므로 0 출력
        res[0] = 1;
        res[2] = 3;

        for(int i=4;i<=N;i++){
            // N이 홀수일 경우 완벽하게 채울 수 있는 경우의 수 없으므로 0 출력
            if(i%2==1) res[i] = 0;
            else{
                // 2블록 당 3개의 경우의 수 존재 = 3
                // 4블록일 경우 새로 추가된 3개의 경우의 수
                // + 2개의 추가 경우의 수(맨 위와 맨 아래에 가로 블록만 놓는 경우) 발생
                // : dp[4] = dp[2]*3 + 2;
                //
                // 6블록일 경우 새로 추가된 3개의 경우의 수
                // + 2개의 추가 경우의 수(맨 위와 맨 아래에 가로 블록만 놓는 경우)
                // + 4블록일 경우의 2가지의 특수 경우의 수 발생 시 양 끝에 2블록 놓을 수 있는 경우의 수의 2배 발생
                // : dp[6] = dp[4]*3 + 2 + dp[2]*2
                //
                // n 블록일 경우 새로 추가된 3개의 경우의 수
                // + 2개의 추가 경우의 수(맨 위와 맨 아래에 가로 블록만 놓는 경우)
                // 4블록부터 n-2블록일 경우의 2가지의 특수 경우의 수 발생 시 양 끝에 n-4 블록 놓을 수 있는 경우의 수의 2배 발생
                // : dp[n] = dp[n-2]*3 + 2 + (dp[2]*2 + dp[4]*2 + ... + dp[n-4]*2)

                // 기존 경우의 수와 독립적으로 추가되는 부분 : 새롭게 추가되는 부분
                // + 2개의 추가 경우의 수(맨 위와 맨 아래에 가로 블록만 놓는 경우)
                res[i] = res[i-2]*3 + 2;

                // 4블록부터 n-2블록일 경우의 2가지의 특수 경우의 수 발생 시 양 끝에 n-4 블록 놓을 수 있는 경우의 수의 2배
                for(int j=4;j<i;j+=2){
                    res[i] += res[i-j]*2;
                }
            }
        }
        System.out.println(res[N]);
    }
}