[Java] 백준 2133번 타일 채우기 - 그림 설명! 이해가 된다고 자부

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

 

홀수에서는 모양이 만들어지지 않으므로 여기서 말하는 "한 단계"는 DP[0], DP[2], DP[4] ... 짝수를 의미한다.

 

그림 1

먼저 DP[2]에서는 3 * 2로 조합 가능한 3가지 경우가 있다.

 

그림 2

DP[4]에서는 DP[2]의 오른쪽에 DP[2]의 경우를 붙인 경우의 수가 모두 있고, (DP[2] * 3)

새로운 특이케이스 2개가 새롭게 존재한다.

 

그림 3

전 단계와 같이 DP[4]의 모양의 오른쪽에 DP[2]를 붙이면 DP[4] * 3의 식이 나오고,

이 과정에서 고려된 특이케이스의 모양은 2)와 같다.

DP[4]의 특이케이스 "오른쪽"에 DP[2]가 붙는 경우만 고려하였으므로 3)처럼 특이케이스 "왼쪽"에 DP[2]가 붙는 경우는 고려되지 않았다.

 

 

즉 3 x 6 에서는

DP[6] =

DP[4] * 3      (전단계에 DP[2]를 붙인 갯수)

 + DP[2] * 2      (그림 3의 3)의 경우에 고려되지 않은 특이케이스를 더함. 여기서 DP[2]는 3)의 왼쪽이며, "2"는 DP[4]에서의 특이케이스 2개를 뜻함)

+ DP[0] * 2      (그림 4의 경우처럼 DP[6]에서 새로 생성된 특이케이스를 아무것도 없는 DP[0] = 1 에 2를 곱함)

 

으로 계산될 수 있다.

그림 4

즉

DP[i] = DP[i - 2] * 3 + DP[i - 4] * 2 + DP[i - 6] * 2 + ... + DP[0] * 2

으로 계산될 수 있다.

 

이 점화식이 DP[2]부터 적용되기 때문에, 초기값은 DP[0]만 있으면 된다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // input
        int N = Integer.parseInt(br.readLine());

        // process
        int[] dp = new int[N + 1];
        dp[0] = 1;
        for (int i = 2; i <= N; i += 2) {
            dp[i] = dp [i - 2] * 3;
            for (int j = i - 4; j >= 0; j -= 2) {
                dp[i] += dp[j] * 2;
            }
        }
        bw.append(String.valueOf(dp[N]));

        // output
        bw.flush();

        br.close();
        bw.close();
    }
}