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

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

 

DP 유형의 기본 문제입니다.

dp[n]은 가로길이가 n개인 바닥을 채울 수 있는 타일의 경우의 수를 의미합니다. 직접 몇개 그려가다보면, 채울 수 있는 타일의 경우가 1x2 직사각형 하나로 끝나는 경우, 2x1 직사각형 두개로 끝나는 경우 두가지입니다. 즉 dp[n]은 가로길이가 n-1개인 바닥을 채울 수 있는 경우의 수 + 가로길이가 n-2개인 바닥을 채울 수 있는 경우의 수입니다. 따라서 다음과 같은 점화식을 도출해낼 수 있습니다.

 

d[n] = d[n-1] + 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] = 2;
    
    for(int i = 3; i <= n; i++) {
    	dp[i] = (dp[i - 1] + 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 2;
	return dp[n] = (D(n - 1) + D(n - 2)) % 10007;
}

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