BOJ/백준-4150-python

문제

풀이

• 피보나치를 구현하면 되는 문제이다.
• 다이나믹 프로그래밍: bottom-up 방식으로 구현하였다.

코드

# https://www.acmicpc.net/problem/4150
# boj, 4150: 피보나치 수, python3
import sys

input = sys.stdin.readline

def solve(n: int) -> int:
    # dp table 할당을 위한 초기화
    d = [0] * (n+1)
    
    # f(1) = 1, f(2) = 1
    d[0], d[1] = 1, 1

    # f(2) 까지의 값이면 dp 수행하지말고 바로 값 return
    if n <= 1:
        return 1

    # dp bottom-up -> fibonacci 구현
    for x in range(1, n+1):
        d[x] = d[x-1] + d[x-2]

    return d[n-1]

if __name__ == '__main__':
    n = int(input())

    print(solve(n))

결과

출처 & 깃허브

boj 4150
github