[백준] C++ 11726(2×n 타일링)

 

#include <iostream>

using namespace std;

int DP[1001];

int main(void)
{
	int a=0;
	cin>>a;
	
	DP[1]=1;
	DP[2]=2;
	
	for(int i=3; i<=1000; i++)
	{
		DP[i]=(DP[i-1]+DP[i-2])%10007;
	}
	
	cout<<DP[a];
	
	return 0;
}

이 문제도 굉장히 간단한 문제이다.

그림으로 설명하겠다.

가로의 길이가 1인 블럭과 2인 블럭이 있기 때문에 이전거와 이이전거만 확인하면 된다.

오른쪽에 블럭을 추가한다고 상상해 보자!!

DP[i]=(DP[i-1]+DP[i-2])%10007