[백준 #1003] 피보나치 함수(Python)
Updated:
이 문제는 피보나치에 관한 문제이다. 하지만 약간 다르다. 문제를 읽어보면 알겠지만 요약하자면 주어진 N을 피보나치 함수로 돌렸을 때, 0과 1이 몇 번 출력되는지를 구하는 문제이다. 이런 문제는 하나씩 써보면 규칙을 금방 찾을 수 있다. 내가 찾은 규칙은 아래와 같다.
- 0번은 (1,0) : 0이 1번, 1이 0번 출력됨
- 1번은 (0,1) : 0이 0번, 1이 1번 출력됨
- 2번은 (1,1) : 0이 1번, 1이 1번 출력됨
- 3번부터는 (2번과 1번의 0의 합, 2번과 1번의 1의 합)
- ...
- k번은 (k-1번과 k-2번의 0의 합, k-2번과 k-1번의 1의 합)
위의 규칙을 코드로 그대로 옮겨 보았다.
Code
import sys
def fibo(n):
if n==0:
print(1,0)
elif n==1:
print(0,1)
elif n==2:
print(1,1)
else:
a=1
b=1
c=0
for _ in range(n-2):
c=b
b+=a
a=c
print(c, a)
T=int(sys.stdin.readline())
for _ in range(T):
N=int(sys.stdin.readline())
fibo(N)
그림을 먼저 그려서 코드를 이해하면 좀 더 편하게 작성할 수 있다. 좀 더 코드 최적화를 하려 했으나 일단은 생각이 안 나므로 끝.
Leave a comment