[알고스팟] 타일링 방법의 수 세기

문제링크

타일링

• 문제
• 답안 제출
• 통계

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • TILING2
  • 1000ms
  • 65536kb
  • 2890
  • 1781 (61%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

2xn 크기의 사각형을 2x1 크기의 사각형으로 빈틈없이 채우는 경우의 수를 구하는 프로그램을 작성하세요.

예를 들어 n=5라고 하면 다음 그림과 같이 여덟 가지의 방법이 있습니다.

경우의 수는 n이 커지면 아주 커질 수 있으므로, 1000000007으로 나눈 값을 대신 출력하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수(C <= 50)가 주어집니다. 그후 C줄에 각각 1개의 자연수로 n(1 <= n <= 100)이 주어집니다.

출력

각 테스트 케이스마다 한 줄에 경우의 수를 1000000007로 나눈 나머지를 출력합니다.

예제 입력

3
1
5
100

예제 출력

1
8
782204094

어떻게 풀까?

그림과 같이 n개의 가로 벽을 세우면, n - 1개를 만드는 경우와 n - 2 개로 나누는 경우를 더하면 n개의 벽에 대한 값을 구할 수 있습니다.

즉, 점화식은 다음과 같습니다.

이는 매우 간단하게 반복문을 통해서 구할 수 있습니다. 그리고, 이 수는 피보나치 수가 됩니다!

이 수는 나중에 매우 커지므로, 문제에서 요구하는 모듈러연산을 이용하는 것을 사용하여 답을 출력합시다!

코드

#pragma once
#include<cstdio>
 
const int INF = 1000000007;
int fibo[101] = { 1, 1};
 
int main()
{
    int t, n;
    scanf("%d\n", &t);
    for (int i = 2; i <= 100; i++)
    {
        fibo[i] = (fibo[i - 1] + fibo[i - 2]) % INF;
    }
 
    while (t--)
    {
        scanf("%d\n", &n);
        printf("%d\n", fibo[n]);
    }
    return 0;
}

여담

fibo[0]과 fibo[1]을 1로 최신화 하고, 반복문에서는 2부터 순환한다는 것이 살짝 중요한 포인트입니다.