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

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

1003번: 피보나치 함수

key로 숫자, value로 (0이 출력되는 횟수, 1이 출력되는 횟수)를 저장하는 counts 딕셔너리를 이용하였다.

fibonacci(0)이 호출되었을 때는 0이 출력되는 횟수가 1, 1이 출력되는 횟수가 0이므로 counts[0]은 (1, 0)으로 초기화하고, 같은 방법으로 counts[1]은 (0, 1)로 초기화 하였다.

 

따라서 counts[i]는 (counts[i-1][0] + counts[i-2][0], counts[i-1][1] + counts[i-2][1])가 된다.

import sys

counts = {0: (1, 0), 1: (0, 1)} # key: num, value: (0이 출력되는 횟수, 1이 출력되는 횟수)

def fibonacci(n):
    if n == 0: return 0
    if n == 1: return 1

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


N = int(sys.stdin.readline())

for _ in range(N):
    n = int(sys.stdin.readline())

    if n in counts:
        print(counts[n][0], end=' ')
        print(counts[n][1])
    else:
        fibonacci(n)

        print(counts[n][0], end=' ')
        print(counts[n][1])