[백준] 2133번: 타일 채우기

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

문제

알고리즘 접근 방법

DP를 이용한다.

3xN의 크기의 벽을 2x1, 1x2로 채우기 위해서는 N이 짝수이어야 한다.
때문에 N이 홀수일 경우 dp[N] = 0 이다.

N이 2씩 늘어날 때마다 생각을 해보겠다.

• N=2 일 경우

dp[2] = 3

• N=4 일 경우
  
  2칸짜리 블럭 * 2칸짜리 블럭 = dp[2] * dp[2] = 9

여기서부터 새로운 모양이 2개가 추가적으로 생긴다.
따라서 dp[4] = 9 + 2 = 11이다.

• N=6일경우도
  마찬가지로
  dp[6] = dp[4] * 3 + dp[6-4] * 2 + dp[6-6] * 2

이런식으로 점화식을 세워보면

N이 짝수일 때
dp[N] = dp[N-2] * 3 + dp[N-4] * 2 + dp[N-6] * 2 + ... + dp[N-N] * 2

따라서 dp[0] = 1로 초기화 해주어야 하며
풀이는 아래와 같다.

풀이

#include <iostream>

using namespace std;

int main(){

    int N, plus;

    cin >> N;

    int dp[N+1] = {0, };

    // 초기식
    dp[0] = 1; // 자기 개수일 경우 새로 생기는 고유한 문양 
    dp[2] = 3;

    for(int i=4; i<=N; i+=2){
        dp[i] = dp[i-2] * dp[2]; // 3 * dp[N-2]
        for(int j=4; j<=i; j+=2){
            dp[i] += dp[i-j] * 2; // 2*dp[N-4] + 2*dp[N-6] + .. + 2*dp[0]
        }
        
    }

    cout << dp[N] << endl;
    
    return 0;
}

정리

처음에 여러 풀이를 봐도 잘 이해가 안갔는데 .. 여러개 보다 보니 도움이 많이 되었다.

💡 참고 포스팅

sw-ko님 블로그
matcha_님 블로그
dontdiethere님 블로그