백준 11726번 C++

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

DP(Dynamic Programming) 의 가장 기초적인 문제이다.

 

dp[i] 를 $2 \times i$ 칸까지 고려했을 때

타일을 깔 수 있는 모든 경우의 수라고 정의하자.

 

$2 \times i$ 의 타일링을 만드는 경우의 수는

다음 그림과 같이 세가지 경로에서 올 수 있는데,

 

 

첫 번째 그림은 dp[i-1] 에 타일 하나를 이어붙이는 경우이고

두 번째 그림은 dp[i-2] 에 타일 두개를 눕혀 한 묶음으로 $2\times2$ 타일을 이어붙이는 경우이다.

이 중 마지막 경우는 사실 dp[i-1]에 포함이 되어있던 경우이므로 무시할 수 있다.

 

따라서

dp[i-1]에 한 타일을 이어붙인 한 가지 경우 + dp[i-2]에 두 타일을 눕혀 이어붙인 한 가지 경우

이 두 경우를 합쳐서 다음과 같은 점화식을 얻을 수 있다.

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

dp[0] = 1, dp[1] = 1 임은 자명하므로

이 두 초기값으로 모든 답을 만들어낼 수 있다.

 

 

아래는 정답 코드이다.

#include <iostream>

using namespace std;

int n;
long long dp[1002];

int main() {
	cin >> n;
	
	dp[0] = 1;
	dp[1] = 1;
	for (int i = 2; i < 1002; i++)
	{
		dp[i] = dp[i - 1] + dp[i - 2];
		dp[i] %= 10007;
	}
	cout << dp[n];
	return 0;
}