백준 1003 : 피보나치 함수 (백준 4150 : 피보나치 수)

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

4150번: 피보나치 수

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

1003번: 피보나치 함수

 

 

해결 방법 : DP

• 가장 기초적인 DP 구현이다.

import sys
input = sys.stdin.readline

def solution(N):
    D = [0] * (N + 1) # dp table
    D[0] = D[1] = 1 # 초기값
    for i in range(2, N): # dp
        D[i] = D[i-1] + D[i-2]

    return D[N-1]

if __name__ == '__main__':
    N = int(input())
    result = solution(N)
    print(result)

 

해결 방법 : DP

• 생각을 조금만 해보면 위 문제와 다를게 없을 것이다

import sys
input = sys.stdin.readline

def solution(N):
    D = [0] * (N + 1) # dp table
    D[0], D[1],  = (1, 0), (0, 1) # 초기값
    for i in range(2, N): # dp
        D[i] = (D[i-1][0] + D[i-2][0], D[i-1][1] + D[i-2][1])

    return D

if __name__ == '__main__':
    T = int(input())
    N = [int(input()) for _ in range(T)]
    result = solution(41) # 최대 경우의 dp table 생성
    for n in N:
        print(*result[n])