[백준] 11726번 - 2×n 타일링

문제

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

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

출력

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

풀이과정

(1) 규칙

가로길이로만 계산하면 되기때문에 세로값 2는 신경쓰지 않습니다.

(2는 (1x2 타일), 1은(2x1 타일) )

n=1	1 (1개)
n=2	2,11 (2개)
n=3	21,12,111 (3개)
n=4	211,121,112,22,1111 (5개)
n=5	2111,1211,1121,1112,221,212,122,11111 (8개)

이와같은 규칙으로 진행되므로, 점화식은 D[N] = D[N-1] + D[N-2] 로 구할 수 있습니다

(2) 순서

메모이제이션을 이용하여 D[N] = (D[N-1] + D[N-2]) %10007를 각 배열에 저장한 뒤 결과를 출력합니다.

(3) 코드

#include <iostream>
using namespace std;
 
long long c;
int memo[1001];//메모이제이션
 
int main()
{
    int n;
    cin >> n;
 
    memo[1] = 1;
    for (int i = 2; i <= (n+1); i++)
        memo[i] = (memo[i - 1] + memo[i - 2])%10007;
    cout << memo[(n+1)] << endl;//1부터 시작했으므로
    return 0;
}