[백준] 2133 타일 채우기 - Dynamic Programming / Java

• 문제 링크

2133번: 타일 채우기

 

• 풀이 과정

문제에 제시된 타일의 크기상 n 이 홀수인 경우에는 타일을 채울 수 없으므로,

n 이 짝수일 때만 경우의 수를 구한다.

 

n = 0 타일을 채울 수 있는 경우는 타일을 채우지 않는 경우의 수 1가지로 dp[0] = 1 으로 초기화,

n = 2 타일을 채울 수 있는 경우는 총 3가지로 dp[2] = 3,

n = 4 타일은 n = 2 의 각각의 경우에 * 3 을 한 dp[2] * 3 = 9 이다.

 

다만 n >= 4 부터 각각에 예외로 추가되는 경우의 수가 2가지씩 존재하므로

결과적으로 dp[4] = dp[2] * 3 + 2 = 11 이 성립한다.

 

n = 6 타일은 위에서 구해진 수식에 대입해보면 dp[6] = dp[4] * 3 + 2 가 구해지고,

6칸 중 4칸의 예외는 마찬가지로 2가지이며 이를 나머지 2칸의 모든 경우의 수와 곱하여 나머지 경우의 수를 구한다.

이를 수식으로 나타내면 dp[2] * 2 이 되며 해당 값을 dp[6] 에 더하여 모든 경우의 수를 구한다.

 

이런식으로 dp[8] = dp[6] * 3 + 2 + dp[4] * 2 + dp[2] * 2 로 나타낼 수 있으며

이를 2중 for 문의 i = 2 ~ n 범위 내부에 dp[i] = dp[i - 2] * 3,

j = i - 4 ~ 0 의 범위 내부에 dp[i] += dp[j] * 2 로 구현하고,

이때 +2 의 경우는 j = 0 일 때 dp[0] = 1 로 초기화하였으므로 1 * 2 = 2 로 구해진다.

 

이 후 3 * n 의 모든 타일을 채울 수 있는 경우의 수가 저장된 dp[n] 을 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

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

        int n = Integer.parseInt(br.readLine());
        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.write(dp[n] + "\n");
        bw.flush();
    }

}