백준 1003번: 피보나치 함수

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

1003번: 피보나치 함수

 

 

 

주어진 N에 대해 피보나치함수를 적용했을때,

0이 출력되는 횟수와 1이 출력되는 횟수를 출력하는 문제임

 

 

먼저 피보나치 수를 알아야함

 

출처 위키백과

출처 위키백과

1 + 1 = 2 ,  2(현재 항) + 1(이전 항) = 3, 3(현재 항) + 2(이전 항) = 5 ......   이런식이다

 

 

피보나치 함수는 L 이라는 list가 피보나치 수를 담는 리스트라고 할때

 

L = []

 

점화식은

L[추가될 항] = L[현재 항] + L[이전 항] 이 된다.

 

 

 

이 문제에서는 0과 1을 출력하는 패턴이 피보나치 수의 패턴이다.

 

0을 출력을 담는 리스트를 L0,

1의 출력을 담는 리스트를 L1이라고 가정하고

만약 입력된 N이 0이면, 0이 1개이므로 L0[0]은 1이고

N이 1이면, 0은 0개, 1은 1개니까

L0[1] = 0,  L1[1] = 1이 된다.

 

아까 점화식이 L[추가될 항] = L[현재 항] + L[이전 항] 이였으니

 

N이  0, 1, 2 번째일경우 미리 리스트에 담아준다

 

L0 = [1, 0, 1]

L1 = [0, 1, 1]

 

import sys
input = sys.stdin.readline

def fibonacci(N):
    #0 출력을 담는 리스트
    L0 = [1,0,1]
    #1 출력을 담는 리스트
    L1 = [0,1,1]
    if N > 2:
        for i in range(2, N):
            # 0과1을 출력하는 list에 각각 (현재항+이전항)을 추가해준다 (fibonacci)
            L0.append(L0[i] + L0[i-1])
            L1.append(L1[i] + L1[i-1])
    # N번째네 0 과 1이 출력되는 횟수를 출력해줌
    print(f'{L0[N]} {L1[N]}')


T = int(input())
for _ in range(T):
    N = int(input())
    fibonacci(N)