[방학의 PS] 다이나믹 프로그래밍 2 - BOJ_1003

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

1003번: 피보나치 함수

 

피보나치 함수가 문제로 나왔습니다. 저는 아무 생각 없이 문제를 풀다가 시간 초과 크리가 뜨고 말았습니다😭. 아무래도 피보나치 함수를 냅다 문제로 냈을 리는 없을 텐데 말입니다. 제가 너무 순진하게 생각했죠ㅎㅎ. 다시 시간 제한을 보니 주어진 시간이 고작 0.25초 밖에 되질 않습니다. 보통 1-2초로 주어진다는 것을 생각하면 매우 짧은 시간이죠. 어떤 방식으로 풀어야 할 것 같으신가요? 피보나치 함수에 시간을 단축한다면? 네, 맞습니다. 다이내믹 프로그래밍을 응용한 문제입니다.

 

우리는 다이나믹 프로그래밍이 문제를 반복되는 단계로 쪼개 앞선 단계의 결과를 뒤에서 재사용하는 알고리즘이라고 며칠 전에 공부했습니다. 그리고 피보나치 함수에서 Bottom-Up 방식을 공부했죠. 오늘의 문제는 Top-Down 방식으로 풀어야 하는 문제입니다. 그래서 오늘은 DP의 Top-Down 방식을 공부해 보겠습니다. 일단 코드부터 살펴봅시다.

 

n = int(input())
memo = [0 for _ in range(n+1)]
 
def fibonacci(n, memo):
    if n <= 1: # n이 0 또는 1인 경우
        return n
    elif memo[n] != 0: # n을 이미 구해서 기억한 경우
        return memo[n]
    else:
        memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
        return memo[n]

 

memo라는 리스트를 만들어서 구한 피보나치 수열을 저장합니다. 재귀 스택을 따라 내려가다가 바닥(n = 0 or 1)에서 올라올 때, memo 리스트에서 값을 기억(저장)해 두었는지 확인하여 불러오는 알고리즘입니다.

 

위의 알고리즘을 숙지하셨다면 오늘의 문제는 쉽게 구현하실 수 있을 것입니다.

 

아래에는 제 정답 코드이나 많이 부끄러운 코드네요ㅎㅎ. 훨씬 좋은 코드가 인터넷에 많습니다.

 

def fib(n, memo):
    if n == 0:
        memo[0] = [1, 0, 0]
        return memo[n]
    elif n == 1:
        memo[1] = [0, 1, 1]
        return memo[n]
 
    if memo[n][2] != -1:
        return memo[n]
    else:
        memo[n] = [fib(n-1, memo)[i] + fib(n-2, memo)[i] for i in range(3)]
        return memo[n]
 
t = int(input())
for _ in range(t):
    n = int(input())
    memo = [[0, 0, -1] for _ in range(n+1)]
    fib(n, memo)
    print(memo[n][0], memo[n][1])