[C/C++] 백준 #1904 01타일(피보나치 수열)

이번 문제는 복잡하게 썼지만, 결국 피보나치 수열을 구하는 문제입니다.

 

Number tiles

 

길이가 N인 01 타일의 이진수를 얻기 위해서는  길이가 N-1인 01 타일의 이진수에 1이 쓰인 타일을 붙이거나 길이가 N-2인 01 타일의 이진수에 00이 쓰인 타일을 붙여야 합니다.  이것을 식으로 표현하면,

 

\[ d_{0} = 1 \]

\[ d_{1} = 1 \]

\[ d_{n} = d_{n-1} + d_{n-2} \]

 

점화식을 보면, 피보나치 수열임을 알 수 있습니다.  단지 시작점이 다른 피보나치 수열이죠.

피보나치 수열을 계산하는 방법은 단순하게 반복문을 돌리는 것이 편합니다.  재귀함수는 아주 시간이 많이 걸리고, 배열을 잡아서 하는 방법도 있지만, 전 그냥 편의상 두개의 변수만을 잡아서 사용했습니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//------------------------------------------------
//    baekjoon #1904
//        - by Aubrey Choi
//        - created at 2019-06-16
//------------------------------------------------
#include <stdio.h>

int fib(int n)
{
    int a = 1, b = 1;
    for(int i = 0; i < n / 2; i++)
    {
        a = (a + b) % 15746;
        b = (a + b) % 15746;
    }
    return (n % 2) ? b : a;
}

int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", fib(n));
    return 0;
}