[백준] 11052, 16194 (파이썬)

저번에 이어 다이나믹 프로그래밍 문제를 풀어나갔다. 오늘 풀어본 문제들은 list 2개를 이용하여 점화식을 만들고 패턴을 파악해야하는 문제들이었어서 상대적으로 난이도가 높게 느껴졌다. 더 많은 유형을 접해보고 해결해야한다. 부트캠프와 병행해서 많이는 하지 못했지만 조금씩이라도 쌓이다보면 도움이 될 것이라고 생각한다.

백준 11052번 카드 구매하기

# 이해하는데 오래걸림, 두 개의 list를 통해서 규칙성을 얻는 새로운 유형
#d[1] = d[0] + p[1]
#d[2] = d[1] + p[1] or d[0] + p[2]
#d[3] = d[2] + p[1] or d[1] + p[2] or d[0] + p[3]
#d[4] = d[3] + p[1] or d[2] + p[2] or d[1] + p[3] or d[0] + p[4]
import sys
N = int(sys.stdin.readline())
P = [0] + list(map(int,sys.stdin.readline().split()))
d = [0]*(N+1)
for i in range(1,N+1):
    for j in range(1,i+1):
        if d[i-j] + P[j] > d[i]:
            d[i] = d[i-j] + P[j]
print(d[N])

백준 16194번 카드 구매하기 2

import sys
N = int(sys.stdin.readline())
P = [0] + list(map(int,sys.stdin.readline().split()))
d = [0]*(N+1)
for i in range(1,N+1):
    d[i] = P[i]
    for j in range(1,i+1):
        if d[i-j] + P[j] < d[i]:
            d[i] = d[i-j] + P[j]
print(d[N])