[백준] 1003 피보나치 함수

백준 1003 피보나치 함수

문제 이해하기

자연수 N이 주어질때 fibonacci(N)을 수행한 결과값에 들어있는 0과 1의 개수를 구하는 문제이다.
문제에 주어진 N번째 피보나치 수를 구하는 C++ 함수는 아래와 같다. (이하 fibonacci()는 f()로 축약하겠다.)

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

 

위 코드를 바탕으로 f(0), f(2), f(3)...의 결과를 도출해보면 아래와 같다.

 

f(0)=0
f(1)=1
f(2)=f(1)+f(0)=1+0
f(3)=f(2)+f(1)=1+0+1
f(4)=f(3)+f(2)=1+0+1+1+0
f(5)=f(4)+f(3)=1+0+1+1+0+1+0+1

 

즉, f(N)의 결과값에 존재하는 0과 1의 개수는 다음과 같다.

 

f(0): 0 -> 1개, 1 -> 0개
f(1): 0 -> 0개, 1 -> 1개
f(2): 0 -> 1개, 1 -> 1개
f(3): 0 -> 1개, 1 -> 2개
f(4): 0 -> 2개, 1 -> 3개
f(5): 0 -> 3개, 1 -> 5개

 

0의 개수는 1, 0, 1, 1, 2, 3...
1의 개수는 0, 1, 1, 2, 3, 5...

 

이런식으로 증가하는 것을 볼 수 있는데 여기에서 0의 개수와 1의 개수에 대한 규칙을 찾을 수 있다.

 

0의 개수와 1의 개수는 각각 초기값으로 1, 0을 가지며 이후부터는

• 0의 개수 = 1의 개수
• 1의 개수 = 0의 개수 + 1의 개수

라는 공식이 성립한다.

따라서 아래와 같은 코드를 작성해서 문제를 해결할 수 있다.

 

풀이

import sys
input=sys.stdin.readline

T=int(input())

for _ in range(T):
  N=int(input())
  countZero, countOne=1, 0
  for _ in range(N):
      # 핵심 부분
    countZero, countOne= countOne, countZero+countOne
  print(countZero, countOne)