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

백준 2133번 문제입니다.

문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

알고리즘 아이디어

이 문제는 동적 계획법(DP) 을 사용하여 해결할 수 있다.

1) DP 배열 정의

• dp[i] = 가로의 길이가 i일때, 경우의 수
• 초기화:
  • dp[0] = 1 (계산을 위한 편의 사항)
  • dp[2] = 3(일반 타일 3가지 경우의 수)

2) 점화식 (Transition) i의 길이일 때, 타일의 경우의 수를 계산

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

• 기본 타일 구성은 다음과 같다.

이때, 길이가 4 이상이 된다면 다음과 같은 특수 타일이 나오게 된다.

• n = 4인 경우

• n = 6인 경우

 

이처럼 특수 타일은 길이가 짝수마다 2개씩 존재하게 된다.

따라서 점화식은 바로 직전 타일에 일반 타일 3개가 더 붙여지는 경우와 특수 타일들이 붙는 경우로 분리된다.

• 일반 타일이 붙는 경우
  • dp[i - 2] * 3
• 특수 타일이 붙는 경우
  • dp[i - 4] * 2 + dp[i - 6] * 2 + ... + dp[0] * 2
  • 이때, dp[0]가 0이면 안되므로 1로 정의한다.

코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    if(n % 2 != 0) {
        return 0;
    }

    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    dp[2] = 3;

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

    cout << dp[n] << endl;

    return 0;
}

혹시라도 틀린 내용이 있다면 댓글로 알려주시면 감사하겠습니다!!