공부/알고리즘
[알고리즘][백준] 16194번 카드 구매하기 2 - 파이썬(python) 풀이
무명오리
2024. 3. 5. 18:48
https://www.acmicpc.net/problem/16194
16194번: 카드 구매하기 2
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
www.acmicpc.net
11502번 카드 구매하기 번외 문제다!
지난주에 돈을 많이 써서 이번에는 최소금액을 구해야한다ㅋㅋ
import sys
n = int(sys.stdin.readline())
p = [0] + list(map(int, sys.stdin.readline().split()))
dp = [0] * 1001
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-j] + p[j], dp[i])
print(dp[n])
그렇게 땡잡았다 하고 단순히 이번에는 max가 아닌 min으로 진행했는데...
dp에 0을 넣었기 때문에 min으로 하면 0이 나오기 때문에 이번에는 False를 넣어줬다
import sys
n = int(sys.stdin.readline())
p = [0] + list(map(int, sys.stdin.readline().split()))
dp = [False] * 1001
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-j] + p[j], dp[i])
print(dp[n])