★DP Intermediate II - 2 Solved★

★ 10826 피보나치 수 4 ★

n=int(input())

def fibo(n):

    if n<2:return n

    a,b=0,1    
    for _ in range(2,n+1):
        a,b=b,a+b
    return b

print(fibo(n))

 

🎋 전형적인 DP 피보나치 수 알고리즘. 이 때, 메모리 효율성을 위해 두 변수 a, b만 설정하고 a+b는 기존 a에 덮어서 메모리 효율 고려. 이 부분만 주의

---

★ 10211 Maximum Subarray ★

import sys
input=sys.stdin.readline

T=int(input())
for _ in range(T):
    N=int(input())
    arr=list(map(int,input().split()))
    if arr[0]<0:
        dp=(arr[0],arr[0])
    else:
        dp=(arr[0],0)
    for i in range(1,N):
        dp=(max(dp[0]+arr[i],arr[i]),max(dp))
    print(max(dp))

🎋 DP 기법 사용할 때, 해당 원소가 반드시 들어가 있을 때와 아닐 때 두가지 케이스로 나눈다. 반드시 들어가 있을 때는 max(앞 원소가 포함했을 때 + 해당 원소, 해당원소만) 이렇게 구하면 된다. 들어가 있지 않을 때는, 앞 원소 dp 두 개중 최댓값으로 업데이트.

---