https://www.acmicpc.net/problem/11726
문제의 직사각형을 채우는 방법은 2*1 조각 1개 또는 1*2 조각 2개 (결국 2*2 모양)를 배치하는 것이다. 즉, 가로 길이가 1 채워지거나, 2 채워진다.
dp(i)를 가로 길이가 i인 직사각형을 채우는 경우의 수라고 정의하자.
가로 길이가 1 채워지는 경우 = dp(i-1)
가로 길이가 1 채워지는 경우 = dp(i-2)
따라서 dp(i) = dp(i-1) + dp(i-2)이다.
이는 피보나치 수열과 동일하고, 코드를 작성할 때 배열이나 벡터를 선언하는 대신 변수 2개에 dp(i-1), dp(i-2)를 저장하면 메모리 차지를 줄일 수 있다.
#include <iostream>
using namespace std;
int main()
{
int n;
int a = 1, b = 2, c;
cin >> n;
if(n == 1) cout << a;
else if(n == 2) cout << b;
else {
for(int i=3; i<=n; i++){
c = (a + b) % 10007;
a = b;
b = c;
}
cout << c;
}
return 0;
}