효율적인 화폐 구성-[이것이 취업을 위한 코딩 테스트다]

📖문제

N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.
예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.

입력 조건

첫째 줄에 N, M이 주어진다. (1 <= N <= 100, 1 <= M <= 10000), 이후 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐 가치는 10,000보다 작거나 같은 자연수이다.

출력 조건

• 첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력한다. 불가능할 때는 -1을 출력한다.

My answer

import sys 
input=sys.stdin.readline

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

coin=[int(input()) for _ in range(n)]

d=[-1]*(m+1)

for i in coin:d[i]=1
    
for i in range(2,m+1):
    for j in range(len(coin)):
        if(coin[j]<=i and d[i-coin[j]]!=-1):
            if d[i] == -1: d[i] = d[i-coin[j]] + 1
            else:d[i] = min(d[i], d[i-coin[j]] + 1)
print(d[m])

Another answer

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())

# DP 테이블을 -1로 초기화
dp = [-1] * 10001

money = []
for i in range(n):
  money.append(int(sys.stdin.readline().rstrip()))
  # 화폐 단위만큼의 금액은 화폐 1개로 만들 수 있다.
  dp[money[i]] = 1

for i in range(1, m + 1):
  # 각각의 화폐 단위 j
  for j in money:
    # DP 테이블의 범위를 넘어가지 않도록 걸어둔 조건문
    if i - j > 0:
      # 금액 (i - j)를 만드는 방법이 존재한다면
      if dp[i - j] != -1:
        # dp[i]값 갱신
        if dp[i] == -1:
          dp[i] = dp[i - j] + 1
        else:
          dp[i] = min(dp[i], dp[i - j] + 1)

print(dp[m])

풀이

이번 문제도 다이나믹 프로그래밍으로 해결하는 문제이며, bottom up 방식으로 해결했다. 

우선 방법을 저장할 d라는 리스트는 전부 -1으로 초기화한뒤에, 화폐 1개로 만들 수 있는 값들은 모두 1로 바꿔줬다.

(화폐 종류가 2,3,5일 때 d[2],d[3],d[5]만 1 나머지는 -1으로) 

아이디어는 화폐 단위를 k라고 했을 때 i원을 만드는 방법은 (i - k)원에다가 k원을 더하는 것이다.

따라서 반복문을 돌면서 우선 i에서 화폐단위인 k를 뺄 수 있을 때(현재 i=2인데, 화페 3을 뺴면 음수)

만약 이전 d[i-k]가 -1이라면, 여기다가 어떤 코인을 더하더라도 만들 수 없기 때문에 지나간다.

d[i-k]가 -1이 아니라면, 우선 현재 d[i]가 초기화 상태인 -1인지 아니면 기존에 화폐 1개로 만들 수 있는 값인 1로 되어있는지 확인하고, 아직 초기상태 -1이라면, 이전 d[i-k]에다가 1을 더해주고, -1이 아니라면 현재 값과 d[i-j]+1 중 문제에서 최소로 화폐를 쓰라했기 때문에 min을 사용하여 구하게 된다.

이번 dp문제도 함수가 돌아가는 과정을 보면서 확인해보자.

 

입력은 2,15 그리고 화폐는 2,3으로 구성되어있다고 하자.(교재예제)

 

1. d=[-1,-1,-1,-1.....,-1] 로 초기화

2. 화폐 단위인 d[2], d[3]만 1로 변경

3. d[1] -> 1이 화폐단위 2,3보다 작음 pass --------------> d[1]=-1

4. d[2] -> d[0]이 존재하나, d[0]=-1 그리고 현재 d[2]=1 -----------> d[2]=1

5. d[3] -> d[0],d[1]이 존재하나, 둘다 -1 그리고 현재 d[3]=1---------------> d[3]=1

6. d[4] -> d[1],d[2]가 존재하고, d[2] != -1이며 현재 d[4]=-1 이므로, d[4]=d[2]+1(2를 만드는 방법에 화폐2 추가) ----> d[4]=2

7. d[5] -> d[2], d[3]이 존재하고, 둘다 -1이 아니며, d[5]=-1 이므로, 우선 d[2]+1로 갱신되고 다음에 d[5]=2이므로,  min(d[5],d[3]+1)을 거쳐 역시 2 -------> d[5]=2

 

이런식으로 반복하다보면 d[15]=3이 나오게 된다.  

위의 코드 맨 마지막에 d를 출력해보면 어떻게 구성되었는지 알 수 있을 것이다.