백준 2133 타일 채우기 (C++)

2133번: 타일

dp를 이용한 문제이다. 먼저 점화식을 생각해내야 한다. 2x1 타일로 채우기 때문에 n이 홀수인 경우는 다 채울 수 가 없다. 즉 n이 짝수인 경우를 생각해야한다.

• n = 2 일 경우, 경우의 수는 3가지
• n = 4 일 경우, n = 2 경우의 수 * 3 + 중간에 2x1이 있는 경우 = 11가지
• n = 6 일 경우, n = 4 경우의 수 * 3 + n = 2이 왼쪽에 있는 경우 * 2 + 중간에 2x1이 있는 경우 = 41가지

위의 결과를 점화식으로 바꿔주어 반복문을 통해 dp[N]을 구해주었다.
이번 문제는 질문 검색을 이용하였다. 아이디어가 떠오르지를 않았다. dp문제를 더 풀어 봐야겠다.

#include <iostream>

using namespace std;

int N;
int dp[31];

void solution(){
    dp[2] = 3;

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

    cout << dp[N];
}

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

    cin >> N;

    solution();

    return 0;
}