백준 1003번 피보나치 함수 - Python

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

풀이

이 문제에서 피보나치 수를 구하는 함수를 제시해준다.
그리고 0과 1이 몇 번씩 호출되는지 출력해야한다.

피보나치 수에 대한 개념을 모른다면 검색해보자.

> 피보나치 수

수학에서, 피보나치 수는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두항의 합인 수열이다.
처음 여섯 항 : 1,1,2,3,5,8 ...
<위키백과>

규칙을 먼저 찾아보자면,

N	0	1	2	3	4	5
zero	1	0	1	1	2	3
one	0	1	1	2	3	5

처음에 zero는 1,0,1로 나열되고 one은 0,1,1로 나열된다.
그 이후의 n번째부터는 피보나치 수열(N2 = N1 + N0)로 나열된다.

그렇다면 이제, 규칙을 가지고 구현해보자.

• 0과 1의 초기배열을 먼저 만들어준다.
• 0은 [1,0,1] 1은 [0,1,1] 로 정해져있음.
• for문으로 초기배열 이후 피보나치 수열로 구한 값을 배열에 추가해준다.
• 각 테스트케이스마다 0과 1의 횟수를 공백으로 출력해야한다.

해답

t = int(input())
zero = [1,0,1]
one = [0,1,1]

def fibo(n) : #[0,1,3]
    if len(zero) <= n :
        for i in range(len(zero), n+1) :
            zero.append(zero[i-1]+zero[i-2])
            one.append(one[i-1]+one[i-2])
    print(zero[n],one[n])

for i in range(t) : #[3]
    a = int(input()) #[0,1,3]
    fibo(a)

이번 문제는 피보나치 수열에 대한 개념을 제대로 알고있다면 쉬운 문제인 것 같다.