[BOJ/Step15] 1003 : 피보나치 함수 (Python)

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

---

피보나치 수 구하는 방법이랑 똑같다

0이 입력되면 0이 한번 출력되고 0번째 fibonacci 수는 1이다

1이 입력되면 1이 한번 출력되고 1번째 fibonacci 수는 1이다

2가 입력되면 0과 1이 한번씩 출력되고 2번째 fibonacci 수는 2이다

…

 

쭉 나열하다 보면 규칙을 알 수 있다.

 

피보나치 수와 같이 n번째 0이 출력되는 횟수는 

n-1번째 0이 출력되는 횟수 + n-2번째 0이 출력되는 횟수이고

n번째 1이 출력되는 횟수는

n-1번째 1이 출력되는 횟수 + n-2번째 1이 출력되는 횟수이다

 

규칙을 알았으니 입력되는 n의 최댓값 40까지 미리 리스트에 0과 1 횟수를 계산하여 저장해 둔다

 

# 1003.py

n = int(input())

fibo0 = [1, 0]
fibo1 = [0, 1]

for i in range(39):
    fibo0.append(fibo0[i] + fibo0[i+1])
    fibo1.append(fibo1[i] + fibo1[i + 1])

for _ in range(n):
    num = int(input())
    print(fibo0[num], fibo1[num])