[Python] 백준 #1003 - 피보나치 함수

문제

---

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

1003번: 피보나치 함수

 

 

 

풀이

---

d = [[0,0] for _ in range(41)]
d[0]=[1,0]
d[1]=[0,1]

for i in range(2,41):
    d[i][0] = d[i-1][0] + d[i-2][0]
    d[i][1] = d[i-1][1] + d[i-2][1]

T = int(input())
for _ in range(T):
    n = int(input())
    print(" ".join(map(str,d[n])))

 

d[n]은 f(n)을 실행했을때 가지는 0의 개수와 1의 개수이다.

 

d[0] = [1,0]

d[1] = [0,1]

 

이다. f(0)일때는 0을 한개 가지고 f(1)일때는 1을 하나 가진다.

 

f(2) = f(1) + f(0)이다.

이때 f(2)의 0의 개수는 f(1) 의 0의 개수와 f(0)의 0의 개수를 합친 것이다.

1의 개수는 f(1) 의 1의 개수와 f(0)의 1의 개수를 합친 것이다.

그러므로 d[2] = d[1] + d[0]이라고 할 수 있다.

 

d[3]은 d[2] + d[1]이다.

 

즉, d[n] = d[n-1] + d[n-2] 라고 표현할 수 있다.