11726번: 2×n 타일링 (BOJ C/C++)

11726번: 2×n 타일링

사용 언어: C

 

문제

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

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

입력

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

출력

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

 

풀이

아래 코드를 좀 수정해서 더 간단하게 쓸 수도 있고 배열로 바꿔서 더 간단하게 쓸 수 있긴하다. 하지만 지금은 귀찮으니 다음부터 더 효율적으로 쓰려고 노력하자! ^^

//n칸짜리를 그냥 1과 2로 어떻게 나눌 수 있냐는 문제
//ex) n=5이면 11111, 1112, 1121, 1211, 2111, 122, 212, 221 
// n=1 -> 1, n=2 -> 2, n=3 -> 3, n=4 -> 5, n=5 -> 8
// 규칙 : d[n] = d[n-1] + d[n-2]

#include <stdio.h>

int main(void)
{
    int n, tmp1=1, tmp2=2, tmp3, ans;
    scanf("%d",&n);

    if(n==1)
        printf("1\n");
    else if(n==2)
        printf("2\n");
    else //n>2
    {
        for(int i=0; i<n-2; i++)
        {
            tmp3 = tmp2;
            tmp2 = (tmp1+tmp2)%10007; 
            tmp1 = tmp3;
        }
        ans = tmp2;

        printf("%d\n",ans);    
    }

    return 0;
}