[백준 알고리즘/Python] 16194 카드 구매하기2

문제

 

문제이해

카드의 개수(N)를 구해야 합니다. 1부터 순서대로 카드팩안에 카드들이 있습니다. 동일한 개수인데 가장 적은 금액을 내야한다고 합니다.

 

일단 카드의 개수 안에서 낼 수 있는 금액들을 추려봅니다. 그 다음 최소값을 구하면 됩니다.

 

ex) 카드 4개를 사야하고 카드팩1 = 1원, 카드팩2 = 5원, 카드팩3 = 6원, 카드팩4 = 7원  인 상황입니다.

카드 1개를 샀을 때 카드팩1 1개이니 1원이 최소값입니다.

카드 2개를 사야할 때 (카드팩1) * 2, (카드팩2) 2개의 상황이 주어지는데 카드팩 2의 금액이 작으니 (카드팩1) * 2를 골라줍니다.

카드 3개를 사야할 때 (카드팩1) * 3, (카드팩2 + 카드팩1), (카드팩3) 3개의 상황이 주어지는데 (카드팩1) * 3이 가장 큰 금액이니 골라줍시다.

카드 4개를 사야할 때 (카드팩1) * 4, (카드팩2 + 카드팩2), (카드팩3 + 카드팩1), (카드팩4) 4개의 상황이 주어지는대 (카드팩1) * 4이 가장 작으니 골라줍니다.

 

이렇게 1부터 차례대로 주어진 상황을 보면서 최소값을 저장하면 됩니다. 그러면 마지막에 들어가는 값은 모든 수의 최소가 들어갑니다.

 

코드

#구할 카드의 개수
card_count=int(input())

#카드팩
card_pack = [0] + list(map(int,input().split()))

for i in range(1,card_count+1):
    li = [] #카드 개수에 따른 상황들
    for j in range(i//2+1):
        li.append(card_pack[i-j]+card_pack[j])
    card_pack[i] = min(li)

print(card_pack.pop())

편의상 카드팩0은 0으로 채웠습니다.

li에는 카드 1개골랐을때, 2개골랐을때... 그 때마다 조합되어지는 카드팩 상황이 담겨집니다.

 

모든 조합되는 카드팩을 구하려면 카드 개수 절반을 나눠가지고 0에서부터 끝까지 조합을 맞춰줍니다. 

ex) i=3 일때 i//2 = 1이므로 for문은 0,1로 돌아집니다. 이전의 카드2개 뽑는 상황의 최소값은 card_pack[2]에 들어있습니다. 그러면 카드 3개를 뽑는 상황일 때 카드 2개 뽑는 상황의 최대값 +  (카드팩3) 의 최소값을 구합니다. 이렇게 되면 card_pack리스트 안에 맨 오른쪽은 모든 상황의 최소값이 나오게 됩니다.