[백준/2294/파이썬] 동전 2

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

2294번: 동전 2

Problem

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

조건

• 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

SOL

동전의 갯수를 세는 문제는 Standard한 예제인 경우가 많다.

위 문제 같은 경우, 그리디한 접근 (보통, 큰 것부터 먼저 주면 동전을 최소가 되도록, 현실세계에서는 구현이 되어있다.)로 되지않는다.

예를들어, 8원을 줘야하는데, 동전이 (1,4,6) 3개의 동전이 있다면, Greedy하게 접근하면, (6,1,1)이 되겠지만, 최소의 동전 갯수라면, (4,4)로 2개가 최소의 동전의 갯수이다.

 

그렇다면, Greedy 하지 않은 접근은 어떻게 할까?

 

아이디어(DP)

일단 , 동전 종류 1개로 8원을 다 나눠줄 수 있는 만큼 나눠준다. 여기선, 순서대로 1원 , 4원, 6원 순서대로 나눠주고, 그 동전으로 각각의 N원을 구성하는 갯수를 최소로 갱신하는 방법으로 테이블을 구성할거다.

이때, Table의 idx는 각 동전의 N원을 나타내고, value는 동전의 갯수를 나타낸다.

 

1원으로 8원을 낼때, 동전의 갯수 

4원으로 8원을 낼때 ,동전의 갯수 

 

이 부분이 핵심이다. idx는 N원을 나타내기 때문에, 4원일 때, 4이하의 idx는 변하지 않는다.

그리고, 4원부터는, idx-4 + 1과, 원래 table의 값을 비교해서, 최솟값을 갱신해준다.

즉, 4원을 (1,1,1,1)으로 구성하는 것보단, (4) 하나로 구성하는게 동전의 갯수를 줄일 수 있다. 그리고 이 대소관계를 비교할 때, 5원이면, (1,1,1,1,1)일텐데, (1,4)로 구성이 가능하므로, 1원 한개에 4원을 추가하는거와 같다. 즉, table[idx-n]을 봐주면 된다. 

for num in seq:
    for i in range(num,M+1):
        DP[i] = min(DP[i-num]+1,DP[i])

 

전체 코드

최솟값을 갱신시켜야 하기때문에, max값을 넣어준다. ( 엄밀히 따지면, 100,001 으로 하면 더 좋겠지만, 100,001보다 큰 값이면 상관이 없기 때문에 그냥 999,999 로 했다.) 

# 동전 
# Not greedy
import sys
input= sys.stdin.readline

N,M =map(int,input().split())
seq = [int(input().rstrip()) for _ in range(N)]
DP = [999999 for _ in range(M+1)]

DP[0] = 0
for num in seq:
    for i in range(num,M+1):
        DP[i] = min(DP[i-num]+1,DP[i])

print(DP[M]) if DP[M] != 999999 else print(-1)