[BOJ] 백준 11727번: 2×n 타일링 2

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

기본적인 DP 문제입니다.

 

#include <bits/stdc++.h>
using namespace std;

const int MOD = 10007;
int n, dp[1001];

void solve(){
	dp[1] = 1;
	dp[2] = 3;
	
	for(int i = 3; i <= n; ++i){
		dp[i] = (dp[i-1] + dp[i-2]*2) % MOD;	
	}
	
	cout << dp[n];
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	
	solve();
}

 

dp 문제는 1) table 정의 2) 점화식 찾기 3) 초기값 설정의 3단계로 일관성있게 풀이합니다.

 

1) table 정의

dp[i] : 2×i 크기의 직사각형을 채우는 방법의 수

 

2) 점화식 찾기

dp[i] = (dp[i-1] + dp[i-2]*2);

1행 1열의 1×1 크기의 직사각형을 채우는 경우는

1×2 타일로 채우는 경우, 2×1 타일로 채우는 경우, 2×2 타일로 채우는 경우로 나눌 수 있다.

1×2 타일로 채우는 경우 2행 1열도 1×2로 채워야한다. 채우고 나면 2×(i-2) 크기의 직사각형을 채우는 문제가 된다. → dp[i-2]
2×1 타일로 채우는 경우 채우고 나면 2×(i-1) 크기의 직사각형을 채우는 문제가 된다. → dp[i-1]
2x2 타일로 채우는 경우 채우고 나면 2×(i-2) 크기의 직사각형을 채우는 문제가 된다. → dp[i-2]

 

3) 초기값 설정
dp[1] = 1;
dp[2] = 3;

 

시간복잡도는 O(n)입니다.