[BOJ / 파이썬] 1003: 피보나치 함수

백준 / BOJ / Python / 파이썬

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

1003번: 피보나치 함수

단계 : 동적 계획법 1

알고리즘 분류 : 다이나믹 프로그래밍

 

풀이:

풀이 방법이 두개가 있다.

 

1. 첫 번째 방법

문제에서 주어진 코드인 fibonacci(N)을 호출했을 때 출력되는 0과 1의 개수를 구하는 문제이다.

0이 출력되는 경우는 N이 0일 때만 출력되며 1이 출력되는 경우는 N이 1일 때만 출력된다.

 

피보나치 수열 구하는 방법은 피보나치 수열에서 자기 이전 두 개 수의 합을 구하는 것이다. n번째 피보나치 수를 구하고 싶다면 n-1번째 피보나치 수와 n-2번째 피보나치 수를 더하면 된다.

 

fibonacci() 함수는 설명한 피보나치 수열의 정의에 따라 구현돼 있는데 이를 다시 보면 fibonacci(N)을 구할 때 출력되는 0과 1의 개수는 fibonacci(N-1)을 구할 때 출력되는 0과 1의 개수와 fibonacci(N-2)를 구할 때 출력되는 0과 1의 개수를 더한 것과 같다.

 

위의 내용을 읽다 보면 결국 출력되는 0과 1의 개수 또한 피보나치 수열을 따르고 있는 것을 알 수 있다.

 

코드

import sys


def solve(n):
    zero = 1
    one = 0
    for i in range(n):
        temp = one
        one += zero
        zero = temp
    print(zero, one)


t = int(sys.stdin.readline())

for i in range(t):
    solve(int(sys.stdin.readline()))

 

2. 두 번째 방법

위의 방법은 동적 계획법이라기보단 그냥 피보나치 수열을 구하는 것에 가깝고 이번에는 조금 더 동적 계획법에 가까운 방식을 이용하겠다. 

 

동적 계획법은 하나의 큰 문제를 작은 여러개의 문제로 나누어 그 작은 여러개의 문제의 결과를 큰 문제를 푸는 데에 이용하는 것이다. 딱 보자마자 피보나치 수열은 앞의 결과를 사용해야하므로 동적 계획법과 아주 어울리는 문제라는 것을 알 수 있다. 

 

물론 재귀를 통해서도 해결할 수 있지만 재귀는 이미 해결된 작은 문제를 그 다음 문제를 풀 때도 끊임없이 처음부터 다시 시작하므로 효율적인 면에서 좋지 못하다. 그와 반대로 동적 계획법은 작은 문제들의 결과를 저장하고 있기 때문에 재귀보다 더 효율적으로 문제를 풀 수 있다.

 

당장 위의 문제와 비교하더라도 위의 문제는 재귀로 풀지는 않았으나 각 테스트 케이스마다 원하는 답이 나올 때까지 피보나치 수열을 처음부터 다시 구한다. 주어진 시간이 짧은 문제였으면 위의 코드로는 통과하지 못했을 것이다.

 

코드

import sys
T = int(sys.stdin.readline())
dp = [[1,0], [0,1]] # 처음 값들을 저장시켜두기
q = [int(sys.stdin.readline()) for _ in range(T)]

for i in range(2,max(q)+1):
    dp.append([dp[i-2][0]+dp[i-1][0], dp[i-2][1]+dp[i-1][1]])
    # 미리 답해야 하는 값 중 가장 큰 값을 찾음을 통해 dp 안에 값을 다 채우기
for i in q:
    print(dp[i][0], dp[i][1])