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

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

11726번: 2×n 타일링

 

이번에도 기본 DP 문제입니다.

 

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

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

void solve(){
	dp[1] = 1;
	dp[2] = 2;
	
	for(int i = 3; i <= n; ++i){
		dp[i] = (dp[i-1] + dp[i-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];

1행 1열에 위치한 1x1크기의 직사각형을 채우는 경우는 1x2 타일로 채우는 경우, 2x1 타일로 채우는 경우가 있다.
1x2 타일로 채우는 경우에는 2행 1열 또한 1x2 타일로 채워야 하므로 채우고 나면 2×(i-2) 크기의 직사각형을 채우는 문제가 된다. (dp[i-2])
2x1 타일로 채우는 경우에는 채우고 나면 2×(i-1) 크기의 직사각형을 채우는 문제가 된다. (dp[i-1])

 

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

 

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