11726 2×n 타일링 C++ 백준

 

다이나믹 프로그래밍 문제이다.

 

 

그림을 그려서 확인했다.

1은 1개니까 1

2는 11 = 이렇게 두개있어서 2개

이후는 이렇게 그려졌다.

점화식이 d[n]=d[n-2]+d[n-1] 이렇게 나왔다.

이후 문제에서 10007의 나머지를 구하라는것을 넣었다.

 

 

#include <iostream>
using namespace std;

int d[10001];
int main()
{
	int n;
	cin >> n;
	d[1] = 1;
	d[2] = 2;
	for (int i = 3; i <= n; ++i)
	{
		d[i] = (d[i - 1] + d[i - 2]) % 10007;
	}
	cout << d[n];

}