[백준/BOJ] 11727번 2×n 타일링 2 (C++)

www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

 

11726번과 거의 비슷한 DP 문제입니다.

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

 

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

 

/* Bottom-Up */

#include <iostream>
using namespace std;

int dp[1001];

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

 

/* Top-Down */

#include <iostream>
using namespace std;

int dp[1001];

int D(int n) {
	if(dp[n] > 0) return dp[n];
	if(n == 1) return 1;
	if(n == 2) return 3;
	return dp[n] = (D(n - 1) + 2 * D(n - 2)) % 10007;
}

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