백준 16194번 카드 구매하기 2 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 16194 카드 구매하기 2

16194 카드 구매하기 2

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

16194번: 카드 구매하기 2

저번 카드 구매하기 문제에서는 카드 n장을 구매 비용을 최댓값으로 구했다면 이번에는 최솟값을 구하는 문제이다.

---

코드

import sys
input = sys.stdin.readline

n = int(input())
p = [0] + list(map(int, input().split()))
dp = [False for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, i+1): 
        if dp[i] == False:
            dp[i] = dp[i-j] + p[j]
        else:
            dp[i] = min(dp[i], dp[i-j] + p[j])
print(dp[n])

---

풀이

input 값들을 받아주고 dp로 활용하기 위한 배열도 선언한다. 길이가 n+1인 dp 배열에 False로 값을 추가하고 활용하는 이유는 min함수를 이용하려 하기 때문이다. (infinity를 사용해도 무방할 듯하다.)

두 개의 for문을 통해 값이 지정되지 않았다면 비교를 위해 먼저 값을 넣고 그 후에 min을 활용하여 더 작은 값을 dp[i] 값으로 활용하는 것이다.

dp[i]는 카드 i장의 카드를 구입하는 최솟값을 저장한다. 즉 i = 3일 때에는 j= 1, 2, 3을 돌며 여러 경우 (1번 카드팩 3개 사는 값, 2번 카드팩 하나와 1번 카드팩 하나를 사는 값, 3번 카드팩 1개를 사는 값)를 비교하여 최솟값을 dp[3]에 저장한다.

출력은 dp의 마지막 요소를 출력해주면 풀이는 끝이 난다.

---

풀이 결과

16194 풀이 결과