[C/C++] 백준 #2193 이친수(수학, 피보나치 수열)

#2193은 수학적 원리를 알고 있으면 쉽게 풀 수 있습니다.

 

문제의 링크는 다음과 같습니다.

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

2193번: 이친수

 

이친수는 0으로 시작하지 않고, 1이 연속으로 나타나지 않는 수입니다.  이것과 관련해서 제가 쓴 글이 있습니다.

https://sdev.tistory.com/319

동전을 n번 던졌을 때, 연속으로 앞면이 나타날 경우의 수는?

동전을 N번 던졌을 때, 연속으로 앞면이 나타나는 경우의 수를 계산하는 방법입니다.  달리 말하면, 총 경우의 수 $2^N$에서 연속으로 앞면이 나타나지 않는 경우의 수를 빼는 것과 같습니다.  바로 이친수 이야기죠.  1이 동전의 앞면이라고 한다면, N개의 숫자를 나열했을 때, 1이 연속으로 나타나지 않는 경우의 수죠.

 

그 경우의 수가 피보나치수와 같다는 것을 설명한 것입니다.

 

Fibonacci Sequence in natural

 

이번 문제는 바로 그 원리를 이용해서 풀 수 있습니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2193
//        - by Aubrey Choi
//        - created at 2019-06-02
//------------------------------------------------
#include <stdio.h>
#include <memory.h>

int main()
{
    int n;
    long long fc0 = 0, fc1 = 1, fp1 = 0;
    scanf("%d", &n);
    for(int i = 1; i < n; i++)
    {
        fp1 = fc1;
        fc1 = fc0;
        fc0 += fp1;
    }
    printf("%lld\n", fc0 + fc1);
    return 0;
}