문제 출처

1. 문제설명

• 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수
• 방법의 수는 10,007로 나눈 나머지 출력

2. 알고리즘 설계

• 2x1 로 사각형을 채우기 위해서는 두 칸을 잡아둬야 하고,
  • 이건 두가지 경우
• 1x2 로 사각형을 채우기 위해서는 한 칸을 잡아두면 된다.
  • 이건 한가지 경우

3. 로직

• 점화식
  • memo[i] = (memo[i-1] + memo[i-2]) % 10007

4. 전체 코드

#include<bits/stdc++.h>
using namespace std;

int n;
int memo[1001];

void DP()
{
	memo[1] = 1;
	memo[2] = 2;

	for (int i = 3; i <= n; i++)
		memo[i] = (memo[i - 1] + memo[i - 2]) % 10007;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	DP();
	cout << memo[n];
}

5. 소감

• 나는 처음에 출력에서 나눠줬는데,
• 생각해보니 DP를 할 때마다 나눠줘야 했다.