[백준/BOJ] 2133번 타일 채우기 (C++)

www.acmicpc.net/problem/2133

2133번: 타일 채우기

 

 

DP 유형으로 이전에 풀었던 타일링 문제와 비슷한데, 살짝 어려워진 유형의 문제였습니다.

맨 오른쪽 끝에 하나를 놓는 경우 2*d[n - 1], 맨 오른쪽 끝에 두개를 놓는 경우 3*d[n - 2]로 다음과 같은 점화식을 도출해낼 수 있습니다.

d[n] = 2*d[n - 1] + 3*d[n - 2]

그러나 주의할 점이 있는데 n = 4일 때 다음과 같이 새로운 모양이 생깁니다.

 

 

이러한 새로운 모양이 n이 4부터 짝수일 때마다 2개씩 생기는게, 이러한 경우를 고려하면 다음과 같은 점화식을 도출해낼 수 있습니다.

 

d[n] = 2*d[n - 1] + 3*d[n - 2] + 2*(d[n - 4] + d[n - 6] + ... + d[0])

 

/* Bottom-Up */

#include <iostream>
using namespace std;

int dp[31];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin>>n;
    
    dp[0] = 1;
    dp[2] = 3;
    int j = 1;
    for(int i = 4; i <= n; i++) {
    	if(i % 2 == 0) {
    		dp[i] = 3 * dp[i - 2];
    		for(int j = 4; j <= i; j++) {
    			if(j % 2 == 0) {
    				dp[i] += 2 * dp[i - j];	
				}
			}
		}
	}
    
	cout<<dp[n];
}

 

/* Top-Down */

#include <iostream>
using namespace std;

int dp[31];

int D(int n) {
    if(dp[n] > 0) return dp[n];
    if(n == 0) return 1;
	if(n == 1) return 0;
	if(n == 2) return 3;
    int result = 3 * D(n - 2);
    for(int i = 4; i <= n; i++) {
        if(i % 2 == 0) {
            result += 2 * D(n - i);
        }
    }
	return dp[n] = result;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin>>n;
    
 	cout<<D(n);
}