[파이썬] 백준 1003 : 피보나치 함수 (실버3)

[파이썬] 백준 1003 : 피보나치 함수 (실버3)

 

1003번: 피보나치 함수

---

문제

---

풀이

방향성 생각

DP문제, 규칙을 나열해보면 알겠지만 0이 호출되는 횟수는 이전 피보나치 수열의 값이다.

다음의 코드로 확인해보면

for i in range(15):
    if i==0 :
        print(1,0)
    else :
        print(an[i-1],an[i])

0이 호출되는 횟수는 n==0을 제외하고 피보나치 수열의 이전 값을 따라가는 것을 볼 수 있다.

1 0
0 1
1 1
1 2
2 3
3 5
5 8
8 13
13 21
21 34
34 55
55 89
89 144
144 233
233 377

 

전체코드

an = [0,1,1,2]
for i in range(37):
    an.append(an[-1]+an[-2])
    
t = int(input())
for i in range(t):
    n = int(input())
    if n==0 :
        print(1,0)
    else :
        print(an[n-1],an[n])