백준 1003번: 피보나치 함수

 

 

 

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

구현 언어: 파이썬

---

import sys
input = sys.stdin.readline

def one_counter(n):

    zero_cnt = [1, 0]
    one_cnt = [0, 1]

    if n <= 1:
        return zero_cnt, one_cnt

    for i in range(2, n+1):
        zero_cnt.append(one_cnt[i-1])
        one_cnt.append(one_cnt[i-1] + one_cnt[i-2])

    return zero_cnt, one_cnt

n = int(input())
zero_cnt, one_cnt = one_counter(40)

for i in range(n):
    num = int(input())
    print(zero_cnt[num], one_cnt[num])

---

시도 횟수: 1

 

구현 포인트:

피보나치 결과를 몇 개 보면, 0의 개수는 n-1의 1의 개수와 같고, 1의 개수는 n-2의 1의 개수와 n-1의 1의 개수를 더한 값과 같다는 것을 확인할 수 있다. 또한 수의 범위가 40까지로 많지 않으므로 미리 답을 모두 담은 리스트를 만들어놓고 입력을 받아 그 리스트에서 답을 출력만 해주는 코드로 작성하였다.