BOJ 1003. 피보나치 함수 (Python)

BOJ 1003. 피보나치 함수

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

1003번: 피보나치 함수

풀이

테스트 케이스에 대해 0이 출력되는 횟수와 1이 출력되는 횟수를 구해보면,

 

테스트 케이스	0이 출력되는 횟수	1이 출력되는 횟수
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5
6	5	8
7	8	13

이렇게 된다. 이는

테스트 케이스(N)에 대한 0과 1의 출력 = (N-1)의 0 출력 갯수 + (N-2)의 0 출력 갯수
                                    (N-1)의 1 출력 갯수 + (N-2)의 1 출력 갯수

임을 알 수 있다.

 

피보나치의 정의는

이것이고 잘 보면 위의 표가 피보나치 수와 매우 유사하다. 즉, 

# 0 출력 횟수
F0 = 1, F1 = 0 인 피보나치 수

# 1 출력 횟수
F1 = 0, F2 = 1 인 피보나치 수

임을 알 수 있다.

 

이것을 매번 구하게 되면 계속 재귀 호출을 해야 하므로 나는 입력받은 수 중에 가장 큰수까지 테스트 케이스에 대한 0, 1의 출력 갯수를 모두 구하고
그저 for문을 돌려 해당 문제에 대한 답을 출력했다.

소스코드

result = [[1, 0], [0, 1]]

N = int(input())
Q = [int(input()) for _ in range(N)]

if max(Q) > 1:
    for i in range(2, max(Q) + 1):
        tmp = [result[i-2][0] + result[i-1][0], result[i-2][1] + result[i-1][1]]
        result.append(tmp)

for n in Q:
    print(result[n][0], result[n][1])