백준 11726번 2xn 타일링 C언어

문제

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

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

입력

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

출력

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

문제 풀이

처음에는 괄호의 수에서 사용한 카탈란의 수 로 푸는 줄 알았다.

근데 이것도 앞의 경우의 수 몇개 풀어보니까 피보나치가 성립되었다.

그리고 계속해서 10007을 모듈 연산하는 것도 잊지 않아야 한다.

#include<stdio.h>
#define SZ 1001
 
int ans_square[SZ];
 
void solution(int n) {
    ans_square[1] = 1; ans_square[2] = 2;
    for (int i = 3; i <= n; i++) {
        ans_square[i] = (ans_square[i - 1] + ans_square[i - 2])%10007;
    }
    printf("%d", ans_square[n]);
}
 
int main() {
    int n;
    scanf("%d", &n);
    solution(n);
}