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

---

0. 문제

 

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

 

1. 아이디어

 

1) 직사각형 타일을 채울 수 있게 기본 단위를 새로 설정한다. (3×2 -> 3개, 3×4 -> 2개)

 

2) 단위 타일이 짝수로만 이뤄져 있으니까 3×N 에서 N이 홀수라면 타일을 채울 수 없다.

 

3) 2, 4, 6, ···로 이어지는 N에서 DP의 값은 이전 DP의 값에 xDP[2]를 하면 된다!

(왜냐면, 길이가 2씩 늘어나므로 2의 길이를 가진 단위 타일을 붙여준다고 생각하면 된다)

 

(핵심) 하지만 이때, 더해지는 2개의 큰 타일덩어리들이 겹쳐지는 부분에서는 길이가 2인 타일이 4인 타일로 바뀔 수 있는 경우도 카운트 해줘야 한다!! ex) dp[8] = dp[6] + dp[2] 가 dp[4] + dp[4]로 바뀔 수도 있다. 이 때, 앞의 덩어리 오른쪽 2와 뒷덩어리 왼쪽 2가 합쳐져서 길이가 4인 타일로 바뀔 수도 있다!

 

2. 소스코드

 

#include <iostream>
int main()
{
    int N, dp[31];
    std::cin >> N;
    for (int i = 1; i <= N; i += 2)
        dp[i] = 0; // 홀수 길이는 불가능!
 
    dp[0]=1, dp[2] = 3; dp[4] = 11;
 
    for (int i = 6; i <= N; i += 2)
    {
        dp[i] = dp[i - 2] * dp[2];
        for (int j = 4; i - j >= 0; j += 2)
            dp[i] += dp[i - j] * 2;
    }
 
    std::cout << dp[N];
}

 

3. 결과

 

 

4. 피드백

 

• (내 생각) DP문제는 이전에 계산했던 값을 다시 사용하는게 핵심이기 때문에, 따로 계산해주지 않아도 무관한 부분을 찾아내는 것도 핵심인듯 하다! 위 문제에서 예를 들자면, 중간 겹치는 부분(길이 4)을 기준으로 앞뒤는 계산하지 않아도 되는 것처럼..

---