문제해설

행의 개수는 2로 고정되어 있고, 열의 개수 N에 따라, 1×2, 2×1 타일로 채우는 경우의 수를 구하는 문제이다.

점화식

타일을 채우는 것에 일정한 규칙이 있음을 발견하고 점화식을 세워 DP로 풀이할 예정이다.
예를 들면,
N = 1일 때, 1x2 타일 * 1개로 채우는 경우로 1가지,
N = 2일 때, 1x2 타일 * 2개 + 2x1 타일 * 2개로 2가지,
N = 3일 때, 뒤를 기준으로 (1x2 타일 * 1개)를 채우고, 앞에 나머지 2개의 열 채우기 + 뒤를 기준으로 (2x1 타일 2개)를 채우고, 앞에 나머지 1개의 열 채우기 = N = 2일 때의 경우의 수 + N = 1일 때의 경우의 수 = 2 + 1 = 3 이다.
(*본인은 뒤를 기준으로 채웠지만 앞을 기준으로 해도 무관하다. 하나의 기준을 가지고 일관되게 규칙을 찾는 것이 가장 중요하다.)

인덱스는 열의 번호 n으로 1에서 N까지의 관계를 다음과 같이 정의할 수 있다.
dp[0] = 0, dp[1] = 1, dp[2] = 2,
dp[3] = dp[2] + dp[1],
dp[4] = dp[3] + dp[2],
...
dp[n] = dp[n-1] + dp[n-2]

모듈러연산

출력 시, Overflow를 방지하기 위해 10007로 모듈러연산을 시행한다. 구현 시, 출력 때만 아니라 매번 모듈러연산을 적용하는데 이에 대한 이유는 2가지가 있다.
1) 출력 때만 적용하면, 중간 연산 과정에서 Overflow가 발생한 것에 대한 대처를 할 수 없다.
2) 모듈러 연산은 분배법칙에 의하여 매번 모듈러연산을 해도 결과는 동일하다.

1. 덧셈의 모듈러 분배법칙:

   (a + b) % m = {(a % m) + (b % m)} % m

2. 곱셈의 모듈러 분배법칙:

   (a * b) % m = {(a * m) + (b * m)} % m

코드

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

int N, dp[1001]; // N의 범위: [1, 1000]

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

    cin >> N;
    dp[1] = 1, dp[2] = 2;
    for (int n = 3; n <= N; n++){ // dp[3] = d[2] + d[1];
        dp[n] = (dp[n - 1] + dp[n - 2]) % 10007;
    }
    cout << dp[N] << "\n";
}