Study/알고리즘

[백준] 16194번_카드구매하기2

혤리 2020. 3. 18. 19:51

문제 링크 : https://www.acmicpc.net/problem/16194

 

16194번: 카드 구매하기 2

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

www.acmicpc.net

n = int(input())
p = [0] + list(map(int,input().split()))
d = [0]*(n+1)
for i in range(1,n+1):
    for j in range(1,i+1):
        if d[i]!=0:
            d[i] = min(d[i],p[j]+d[i-j])
        else:
            d[i] = p[j]+d[i-j]
print(d[n])

또는 if-else 대신

n = int(input())
p = [0] + list(map(int,input().split()))
d = [0]*(n+1)
for i in range(1,n+1):
    for j in range(1,i+1):
        if d[i]==0 or d[i]>p[j]+d[i-j]:
            d[i] = p[j]+d[i-j]
print(d[n])