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

 

 

<코드>

#include<iostream>
#include<algorithm>
using namespace std;

int n, dp[1001];

int main()
{
	dp[1] = 1;
	dp[2] = 2;
	cin >> n;

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

 

풀이 방법

 

2xn 타일을 채우는 방법을 생각해보면 

 

2x(n-1) 타일 맨 뒤에 2x1타일을 세로로 1개 넣는 방법의 수와
2x(n-2) 타일 맨 뒤에 2x1타일을 가로로 2개 넣는 방법의 수의 합이라고 볼 수 있다.

 

 

Q. 2x(n-2) 타일 맨 뒤에 2x1타일을 세로로 2개 넣는 방법의 수도 존재하지 않나요???

 

A. 2x(n-2) 타일 맨 뒤에 2x1타일을 세로로 2개 넣는 방법의 수는
    2x(n-1) 타일 맨 뒤에 2x1타일을 세로로 1개 넣는 방법의 수에 포함되므로 따로 더해주지 않아도 됩니다.

 

따라서 초기값 dp[1]과 dp[2]를 설정해주고 점화식을 세우면 아래와 같습니다.

dp[i] = dp[i - 1] + dp[i - 2];

 

 

www.acmicpc.net/problem/11726

11726번: 2×n 타일링