[c++] 백준 11726번 - 2*n 타일링

# 백준 11726번 URL

11726번: 2×n 타일링

 

다이나믹 프로그래밍 문제의 기본이라고 할 수 있는 '타일링' 문제이다.

 

기본적으로 다이나믹 프로그래밍에서는 규칙성을 찾아서 점화식을 찾는게 관건이라고 할 수 있다.

 

먼저, 수많은 타일이 이미 쌓여있고 1만큼 추가한다고 가정해보자!

 

위와 같은 경우, 이미 이전에 d(n-1)가짓 수로 타일을 배치한 상태에서 1가지의 방법으로 밖에 타일을 놓지 못한다.

 

두번째로, 2만큼 타일을 추가한다고 생각해보자.

 

이렇게 타일을 쌓는 방식은 앞서 고려했던 경우와 같으므로 고려하지 않으며

 

이 경우만 계산! 결과적으로 d(n) = d(n-1) + d(n-2)라는 수열 점화식이 생성된다.

 

#include <iostream>

using namespace std;

int d[10001];

int block(int n) {
	if (n == 1) return 1;
	else if (n == 2) return 2;
	else {
		if (d[n] != 0) {
			return d[n];
		}
		return d[n] = (block(n - 1) + block(n - 2)) % 10007;
	}
}

int main() {
	int num = 0;
	scanf("%d", &num);
	printf("%d", block(num));
	
}