효율적인 화폐 구성

1. 문제 설명

출처 : 이코테2021

---

2. 문제 조건

• 2가지(N)으로 총합 15(M)을 만들기 위해 2원화폐와 3원화폐
• 3가지(N)으로 총합 4(M)을 만들기 위해 3,5,7원 화폐

---

3. 문제 해결 아이디어

 

[Step 0]

• N = 3, M = 7이고, 각 화폐의 단위가 2, 3, 5인 경우를 확인
• 초기화 작업
  • 먼저 각 인덱스에 해당하는 값으로 INF(무한)의 값을 설정
  • INF는 특정 금액을 만들 수 있는 화폐 구성이 가능하지 않다라는 의미
  • 10,001을 사용가능
    • 1~7까지는 만들수 없는 무작위의 값을 설정

• 인덱스(0) = 0원을 만들기 위한 최소한의 화폐 개수는 0

 

[Step 1]

• 첫 번째 화폐 단위인 2를 확인한다.
• 점화식에 따라서 다음과 같이 리스트가 갱신된다.

• 인덱스 2원을 만들 수 있는건 1개
• 인덱스 4원을 만들 수 있는건 2개(2원 2개)
• 인덱스 6원을 만들 수 있는 건 3개(2원 3개)
• 반면 1,3,5원은 만들 수 없다.

 

[Step 2]

• 두 번째 화폐 단위인 3을 확인한다.
• 점화식에 따라 리스트를 갱신시킨다.

• 인덱스 3, 6원을 만들기 위해 각각(1개, 2개가 필요하다.)
• 7원은 기본적으로 만들 수 없었지만 단위가 3인 화폐를 이용하고 있으므로 앞으로 3칸 움직여 (인덱스 4)의 값을 가져와 1을 더해준다.

 

[Step 3]

• 세 번째 화폐 단위인 5를 확인한다.
• 점화식에 따라 리스트를 갱신시킨다.

• 인덱스 5원은 2개에서 1개로 바뀌었고 7원또한 화폐단위가 5이므로 5칸 앞으로가서 (인덱스 2원)의 값에 1을 더한다.

---

4. 답안

n, m = map(int, input().split())
#n개의 화폐 단위 정보를 입력받기
array = []
for i in range(n):
    array.append(int(input()))

#DP 테이블 초기화
d = [10001] * (m + 1)

#바텀 업방식
d[0] = 0
for i in range(n):
    for j in range(array[i], m + 1):
        if d[j - array[i]] != 10001:#(i - k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j - array[i]] +1)
#계산된 결과 출력
if d[m] == 10001: #최종적으로 M원을 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])

• 화폐의 개수n, 만들고자 하는 값 m을 작성
• 각각의 화폐의 단위를 확인하므로 for문을 중첩