[C++] 백준 2133번 : 타일 채우기 (S2)

#문제

www.acmicpc.net/problem/2133

2133번: 타일 채우기

#풀이 & 학습한 내용

이번문제에서 가로길이가 0일때의 경우의 수를 1로 설정해줘야한다. 그리고 가로길이가 홀수일때는 총 타일수가 홀수 개가 되므로 항상 경우의 수가 0이다. 마지막에 어떤 타일로 끝날 수 있는지 분석해야하는 과정이 쉽지 않다. 점화식을 세우고 base케이스를 채운 뒤 for문을 통해 dp배열을 채워나가 답을 구했다.

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int dp[32];
 
int main(void) {
    int N;
    cin >> N;
    dp[0] = 1;
    dp[2] = 3;
    for (int i = 3; i <= N; i++) {
        if (i % 2 != 0) {
            dp[i] = 0;
        }
        else {
            dp[i] += 3 * dp[i - 2];
            for (int j = 4; i-j>=0; j++) {
                dp[i] += 2 * dp[i - j];
            }
        }
    }
    cout << dp[N] << '\n';
}

 

github.com/HoYoungChun/BOJ_algorithm/blob/master/Dynamic_Programming/BOJ_2133.cpp

HoYoungChun/BOJ_algorithm