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

1003번 : 피보나치 함수

 

생각보다 애를 먹었던 문제이다. 규칙성을 찾을 생각은 하지 않고 무작정 0을 호출하면 변수에 1을 더해야지! 라는 생각에 갇혀있었던 것 같다. 이후 0을 호출하는 수의 규칙성을 찾아보았는데, 문제를 아주 쉽게 풀 수 있다.

 

n	0	1	2	3	4	5	6	7	8
0 호출	1	0	1	1	2	3	5	8	13
1 호출	0	1	1	2	3	5	8	13	21

 

이를 확인하면 규칙성을 쉽게 발견할 수 있다. 먼저 1 호출은, 그냥 해당 피보나치 수와 값이 같다. 애초에 재귀를 통해 푸는 풀이에서 어떤 피보나치 수를 매개변수로 넘기던, fibo(1)을 수많이 호출하고 더해서 해당 값을 만들기 때문이다.

 

0을 호출하는 횟수는 제일 앞이 0 으로 시작하는 것만 제외하면 1 호출과 같은 순서를 띄고 있다.

 

그러면 결국 어떤 수 n 에서 fibo(1) 과 fibo(0) 호출 횟수는 각각 fibo(n)과 fibo(n-1) 이다

 

이를 적용하면 다음과 같이 2가지로 풀 수 있다.

 

내 코드(for 사용):

import sys
input = sys.stdin.readline

def fibo(n):
    if n < 2:
        return n
    
    a, b = 0, 1
    for _ in range(n-1):
        a, b = b, a + b
    
    return b

T = int(input())
for _ in range(T):
    n = int(input())
    print(1 if not n else fibo(n-1),fibo(n))

 

for 문과 매핑을 사용하여 피보나치 수를 구할 수 있다. 시간 복잡도도 재귀를 쓸 때와 달리 O(n) 밖에 되지 않는다. 출력은 n 이 0 인 경우 하나만 제외하고 일반적으로 출력해주면 된다.

 

내 코드(DP):

import sys
input = sys.stdin.readline
req = [int(input()) for _ in range(int(input()))]
dp = [0,1]
for i in range(2,max(req)+1):
    dp.append(dp[i-2]+dp[i-1])
for n in req:
    if n == 0:
        print(1, 0)
        continue
    print(dp[n-1], dp[n])

dp list에 피보나치 수를 저장하면서 구할 수 있다. 요청한 값들 중에서 가장 큰 수까지의 피보나치 수를 구하고, 출력은 n과 n-1의 값을 출력해주면 된다. 단 n == 0 인 경우는 따로 분리해준다.

 

 

문제를 처음 접했을 때 상당히 고민했는데, 앞으로는 DP로 풀 수 있을 것 같으면 규칙성을 먼저 확인해봐야 할 것 같다.