11726번: 2×n 타일링

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

타일의 맨 오른쪽을 채우는 방법은 세로로 세운 타일을 한 개 사용하는 방법(1)과 가로로 눕힌 타일을 두 개 사용하는 방법(2) 두 가지가 있다. 따라서 2×1 크기부터 2×(n - 1) 크기의 타일을 채우는 방법을 모두 알고 있을 때, 2×n 크기의 타일을 채우는 방법은 2×(n - 1) 크기의 타일을 먼저 채운 뒤 오른쪽에 1번 방법을 사용하는 것과, 2×(n - 2) 크기의 타일을 먼저 채운 뒤 오른쪽에 2번 방법을 사용하는 것 두 가지 방법으로 나눌 수 있다.

#include <cstdio>

#define MAX_N 1000
#define MOD 10007
#define get(i) (arr[i][0] + arr[i][1]) % MOD

int main() {
    // 만들고자 하는 타일의 길이
    int n;
    // arr[i - 1][j]: 2 * i 크기의 타일을 (j ? = : |)로 끝내는 경우의 수
    short arr[MAX_N][2] = {{1, 0}, {1, 1}};

    // 만들고자 하는 타일의 길이를 입력받은 뒤
    scanf("%d", &n);

    // 길이 2부터 차례로
    for (int i = 2; i < n; i++) {
        // 끝에 |가 붙는 길이가 i인 타일은 길이가 i - 1인 타일의 맨 뒤에 |를,
        // 끝에 =가 붙는 길이가 i인 타일은 길이가 i - 2인 타일의 맨 뒤에 =를 붙여 생성
        arr[i][0] = get(i - 1);
        arr[i][1] = get(i - 2);
    }
    
    // 길이가 n인 타일을 만드는 경우의 수를 출력
    printf("%d\n", get(n - 1));

    return 0;
}