[백준] 16194: 카드 구매하기 2 (Python)

문제📖

풀이🙏

• 카드 구매하기와 다르게 최솟값을 구하는 것이 목적이므로
• dp 테이블을 위한 점화식에서 tmp를 이용하여 가장 최솟값을 구하여 저장한다.

코드💻

n = int(input())
data = list(map(int, input().split()))

dp = [0] * (n+1)
dp[0] = 0
dp[1] = data[0]

# dp[2] = dp[1] + data[0] or dp[0] + data[1]
# dp[3] = dp[2] + data[0] or dp[1] + data[1] or d[0] + data[2]
# dp[4] = dp[3] + data[0] or dp[2] + data[1] or dp[1] + data[2] + dp[0] + dp[3]
for i in range(2, n+1):
    for j in range(1, i + 1):
        if j == 1:
            tmp = dp[i - j] + data[j-1]
        if tmp > dp[i - j] + data[j-1]:
            tmp = dp[i - j] + data[j-1]
    dp[i] = tmp
print(dp[n])