2×n 타일링 //11726

• 문제
  
  // 시간 제한: 1초, 메모리 제한: 256MB

• 입력
  첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

• 출력
  첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

// Created by dongwan-kim on 2022/08/14.
#include<iostream>

#define MOD 10007
using namespace std;

long long int n, dp[1000];

int main() {
    cin >> n;

    dp[0] = 1;
    dp[1] = 2;
    for (int i = 2; i < n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;		//점화식
    }

    cout << dp[n - 1];
}

풀이

dp알고리즘을 이용하여 문제를 해결했다.

이 문제는 생각보다 단순하게 풀었다.
처음 접근했을 때는 n이 짝수 일때와 홀수일때 나눠서 n-1번째 직사각형 채우는 방법 수 곱해주고 뭐 이런식으로 점화식을 계산해보고 쭉 나열해서 보니 시작이 1 2 인 피보나치 수열 형식이 규칙인 것을 깨닫고 구현하였다.

문제에서 10007로 나눈 수를 출력하라고 되어있어서 MOD에 define해주어서 dp배열에 삽입할 때 MOD한 수를 넣어 주었다.