[백준]Baekjoon11726(Dynamic Programming)

풀이

기저조건 :

n = 1일 때, f(n) = 1

n = 2일 때, f(n) = 2

점화식 :

2 x 1 타일의 경우 무조건 2개를 사용하면서 2x2 정사각형을 만듦

1 x 2 타일의 경우 전에 있었던 타일로부터 그냥 하나씩 붙이면 됨

고로 f(n) = f(n-2) + f(n-1) 

그리고 답이 10007로 나눈 나머지이므로 반복문에서 계속 mod연산을 수행한다.

(미리 mod 연산을 해도 최종 답에 영향을 미치지 않음)

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

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