본문 바로가기

컴퓨터/Online Judge

[acmicpc.net] 1003 피보나치 함수

문제 링크 : https://www.acmicpc.net/problem/1003


문제 내용


fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.


fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.


fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.


두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.


fibonacci(0)은 0을 출력하고, 0을 리턴한다.


fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.


첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.


fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.


이 때, 1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.


소스코드


fibo = [[1, 0], [0, 1]]
 
def fibonacci(N, res):
    for i in range(N):
        if i<len(res):
            continue
        res.append([res[i-2][0]+res[i-1][0], res[i-2][1]+res[i-1][1]])
    return res
 
fibonacci(41, fibo)
 
T = int(raw_input(""))
 
for i in range(T):
    N = int(raw_input(""))
    res = fibo[N]
    print(str(res[0])+" "+str(res[1]))


'컴퓨터 > Online Judge' 카테고리의 다른 글

[acmicpc.net] 2167 2차원 배열의 합  (0) 2016.09.11
[acmicpc.net] 2579 계단 오르기  (0) 2016.09.09
[acmicpc.net] 2193 이친수  (0) 2016.09.08
[acmicpc.net] 1463 1로 만들기  (0) 2016.09.07
[acmicpc.net] 1149 RGB거리  (0) 2016.09.06
[acmicpc.net] 1003 피보나치 함수  (0) 2016.09.01