동전 2

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

2294번: 동전 2

문제요약:

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

 

난이도:

골드5

 

소요시간:

20분

 

제출횟수:

2회

 

코딩:

import sys
input = sys.stdin.readline

n,k = map(int,input().split())

coin = set()
for _ in range(n):
    coin.add(int(input()))
coin = sorted(list(coin))

arr = [[0]*len(coin) for _ in range(1+k)]
for x in range(len(coin)):
    for y in range(1,1+k):
        if y==coin[x]:
            #코인과 딱맞다면
            arr[y][x] = 1
        elif y>coin[x]:
            #코인보다 크다면
            if arr[y-coin[x]][x]:
                #이코인을 고르고 남았은걸 채울 수 있다면,고를건지 말건지
                if arr[y][x-1]:
                    #이전코인으로도 채울수 있다면, 새로운 코인을 쓰는게 이득인지,기존이 이득인지
                    arr[y][x] = min(arr[y-coin[x]][x] +1,arr[y][x-1])
                else:
                    #무조건 새코인을 쓰는게 이득
                    arr[y][x] = arr[y-coin[x]][x] +1
            else:
                #첫코인이 아니라면
                arr[y][x] = arr[y][x-1]
        else:
            #코인보다 작다면
            arr[y][x] = arr[y][x-1]
                
print(arr[-1][-1] if arr[-1][-1] != 0 else -1)
#고를 수 없다면 -1

저번에 풀었던 knapsack알고리즘과 비슷한 문제이다. 선택의 여부에 따라 n*m 2차원 배열을 채워나가는 알고리즘인데, 저번 방법과 똑같이 x축은 코인의 종류, y축은 선택한 돈이다. 이에 따라 선택한 코인과 같다면 무조건 1개이므로 1을 채우고, 그보다 크다면 그값을 뺀 값중에 0 이아닌 작은 것을 택한다.(이 코인을 선택할지말지 고민후)  그렇게 모든 2차원 배열을 돈 후 arr[-1][-1]이 0이 아니라면(고를수 있다면) 그것을 출력하고 아니라면 -1을 출력한다. (그 숫자를 구현할 수 없다)

원래 이런 DP를 어려워 했는데 이제 항상 선택을 할지 말지에 따라 나눈다 라는 개념이 (knapsack) 머리속에 있으니 생각보다 쉽게 풀 수 있었다.

 

다른사람 코드:

from sys import stdin

n, k = map(int, stdin.readline().split())

li =[]

for i in range(n):
   li.append(int(stdin.readline().rstrip()))

dp = [10001] * (k+1)
dp[0] = 0

for num in li:
   for i in range(num, k+1):
       dp[i] = min(dp[i],dp[i-num]+1)
if dp[k] == 10001:
   print(-1)
else:
   print(dp[k])

1차원 배열을 사용한후 전체를 큰수로 채워준뒤 dp[0]만 0으로 만들어 줍니다. 그후 작은 코인부터 선택한 후 코인의 크기부터 시작합니다. 그후 원래있는것을 선택할지 코인만큼 뺀곳+1을 선택할지 고민하는데, 이때 처음이라면 dp[i-num]이 0이기 때문에 1을 선택하게 되고, 둘다 선택 불가여도 10001을 고르게 되고, 둘중 하나만 선택가능하다면 자동으로 작은것을 선택하게 돼서 논리의 빈공간이 없게 됩니다.