문제 출처 : https://www.acmicpc.net/problem/24416

문제 파악

피보나치 수열에 대해 재귀호출 방식과 dp방식으로 각각 풀어보고
각 함수 호출이 몇번씩 일어나는지 파악하며 출력하는 문제이다.

해답 및 풀이

import sys
input = sys.stdin.readline

n = int(input())

req_cnt = 0

def fib_req(n):
    global req_cnt
    if n == 1 or n == 2:
        req_cnt += 1
        return 1
    
    else:
        return (fib_req(n-1) + fib_req((n-2)))
    
fib_req(n)
print(req_cnt)


dp = [None] * n
dp_cnt = 0
def fib_dp(n):
    global dp_cnt
    dp[0], dp[1] = 1, 1

    for i in range(2,n):
        dp[i] = dp[i-1] + dp[i-2]
        dp_cnt +=1 

    return dp[n-1]

fib_dp(n)
print(dp_cnt)    

무작정 문제에서 제시한 수도코드를 통해 코드를 구현하고 각각 req_cnt,db_cnt 에 담아 출력했는데 예상출력은 나왔지만 시간초과가 나왔다.

그러나 pypy3으로 돌려보니 정답이 나왔고 이 문제는 사실 취지가

30번째 피보나치 수열을 구하는데 있어서 재귀호출은
832040 만큼 돌아야하지만 dp는 메모이제이션을 통해 28번만 돌면 된다는 것을 알려주기 위한 문제이기 때문에 pypy3 정답을 확인하고 넘어갔다.

파이썬 정답을 위한 코드는 다음과 같다.

n = int(input())

# 반복문이 몇 번 실행되는지는 이 구현에서 for문 반복 횟수로 측정 (n-2번)
def req_count(n):
    return n - 2  # i = 3부터 n까지 돌기 때문

# fib(1) 또는 fib(2)가 호출되는 횟수는 n번째 피보나치 수와 같다
def dp_count(n):
    dp = [0] * (n+1)
    dp[1] = dp[2] = 1
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print(req_count(n), dp_count(n))