[C++] 백준 2133: 타일 채우기

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

 

문제의 설명이 매우 단순하니만큼 시뮬레이션을 돌려봐야 할 거 같다는 생각이 들었다.

dp[i] = 3 * i 크기의 벽을 타일로 채우는 경우의 수

로 가정하고, 차근차근 N = 1부터 진행해보자.

 

풀이

N = 1

2 * 1과 1 * 2의 타일로는 3 * 1을 채울 수 없다.

즉 dp[1] = 0

 

 

N = 2

 

로 총 3가지의 모양이 나온다.

즉 dp[2] = 3

 

 

N = 3

역시 타일을 채울 수 없었다.

여기까지 했으면 N에 홀수가 들어갈경우 dp배열의 값이 0이라는 걸 추측이 가능하다.

 

 

N = 4

중앙을 기준으로 나눴을 때, dp[2] * dp[2] = 9라는 걸 알 수 있다.

그럼 dp[4] = 9인걸까???

 

답은 아니다이다.

문제의 힌트를 유심히 보면

4칸짜리에 특수한 모양이 있다.

이 모양을 생각하면 2를 추가로 더해줘야 한다.

즉 dp[4] = dp[2] * dp[2] + 2 =  11이 된다.

 

 

N = 5(생략)

 

 

N = 6

3 * 6을

3 * 4 와 3 * 2의 결합된 형태로 보면

dp[4] * dp[2]를 통해 경우의 수로 구할 수 있다.

 

그럼 이게 끝일까?

.

.

.

아니다!!!

3 * 2와 3 * 4의 결합된 형태도 존재한다.

그럼 dp[2] * dp[4]를 한 번 더 더해줘야 되는구나~~

할 수 있지만,,,

 

3 * 4는 3 * 2와 3 * 2로 또 나눌 수 있으므로,

사실 위에서 구한 경우의 수와 중복된 형태가 많이 존재할 것이다.

 

그럼 다 중복인건가??? 싶지만

dp[4]를 구할 때 봤듯이 4칸짜리 특수한 모양이 두 개 존재한다.

즉, dp[2] * 2를 더해줘야 되는 것이다.

 

 

그럼 dp[6] = dp[4] * dp[2] + dp[2] * 2네!

라고 넘어가선 안된다.

 

N =  4의 경우와 마찬가지로

N = 6의 경우도 6칸짜리 특수한 모양이 2개 존재한다.

그래서 dp[6] = dp[4] * dp[2] + dp[2] * 2 + 2이다.

 

 

여기까지 했으면 대략 규칙이 감이 잡힐테지만 한 번만 더 해보도록 하자.

 

 

N = 8

3 * 8은

3 * 6과 3 * 2, 3 * 4와 3 * 4, 3 * 2와 3 * 6, 그리고 3 * 8으로 경우의 수를 나눌 수 있다.

 

1. 3 * 6과 3 * 2

= dp[6] * dp[2]로 쉽게 구할 수 있다.

 

2. 3 * 4와 3 * 4는

dp[4] * dp[4]이 아니라는 것을 N = 6에서 확인할 수 있었다.

중복된 경우의 수가 굉장히 많을 것이다.

3 * 4 하나가 특수한 모양을 띨 때, 3 * 6과 3 * 2의 경우에서 없는 경우일 것이다!!!

즉, dp[4] * 2이다.

 

3. 3 * 2와 3 * 6

역시나 중복된 것을 제외하면 3 * 6이 특수한 모양일 때만 남을 것이다!!

즉, dp[2] * 2이다.

 

4. 3 * 8

특수한 모양을 생각해보면 2이다.

 

이 값들을 다 더하면 dp[8] = dp[6] * dp[2] + dp[4] * 2 + dp[2] * 2 + 2 이라는 걸 알 수 있다!

 

 

점화식 구하기

dp[2] = 3

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

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

dp[8] = dp[6] * dp[2] + dp[4] * 2 + dp[2] * 2 + 2

나열해보니 규칙이 확실히 보인다.

 

 

dp[n] = dp[n-2] * dp[2] + dp[n-4] * 2 + dp[n-6] * 2 + ... dp[0] * 2

(dp[0] = 1이라고 했을 때)

 

점화식까지 구했으니 코드로 구현만 하면 된다!

 

 

전체 코드

#include <iostream>
#include <algorithm>
using namespace std;

int dp[34];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin>>n;

    dp[0] = 1;
    dp[2] = 3;
    for(int i = 4; i <= n; i+=2){
        dp[i] = dp[i-2] * dp[2];
        for(int j = i-4; j >= 0; j -= 2){
            dp[i] += dp[j] * 2;
        }
    }

    cout<<dp[n];
    return 0;
}

dp[0]과 dp[2]에 초기값을 넣는 것만 주의해서 코드를 짜면 성공적으로 AC를 맞을 것이다.