[백준] 2748. 피보나치 수 2 - 문제 풀이 (+파이썬 코드)

Question. 백준 2748. 피보나치 수 2

 

 

 

 

 

---

Answer.

 

사실 이 문제는 파이썬에서는 "백준 2747. 피보나치 수" 문제와 동일하다.

파이썬은 int, long 구분을 할 필요가 없고, 숫자가 아무리 커져도 다 담을 수 있기 때문에 

2747번에 pass한 코드를 그대로 제출하면 된다.

 

그러나 cpp, java의 경우 long long 등으로 선언해,

피보나치 수의 값이 int 범위를 넘어갈 경우에도 해당 값을 담을 수 있도록 해야 pass 한다.

 

아래 파이썬 코드는 [백준] 2747. 피보나치 수 - 문제 풀이 (+파이썬 코드)과 동일하다.

 

 

sol 1) recursion with memoization

 

# recursion with memoization
# time complexity : O(N)

def solve(n: int) -> int:
    dp = [0, 1] + [-1] * (n+1)  # 0, 1 값 저장(종료조건) 및 -1로 초기화(not visited)

    def fibo(n: int) -> int:
        # 이미 방문한 노드인 경우
        if dp[n] != -1:
            return dp[n]

        # memoization하며 방문
        dp[n] = fibo(n-1) + fibo(n-2)
        return dp[n]

    ans = fibo(n)
    return ans

n = int(input())
print(solve(n))

 

 

sol 2) for문 이용해 구현

 

# for문 이용해 구현
# time complexity : O(N)

def fibo(n):
    dp = [0, 1]
    for _ in range(2, n+1):
        dp.append(dp[-1] + dp[-2])
    return dp[n]

n = int(input())
print(fibo(n))

 

풀이법	time complexity	space complexity
sol 1)  recursion with memoization	O(N)	O(N)
sol 2)  for문 이용해 구현	O(N)	O(N)