[알고리즘] #05 다이나믹 프로그래밍-효율적인 화폐 구성

🛠 '효율적인 화폐 구성' 문제

🔧  문제 

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

 

- 입력조건 

: 첫째 줄에 N, M이 주어진다(1<= N <= 100, 1 <= M <= 10,000)

: 이후 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐 가치는 10,000보다 작거나 같은 자연수이다.

- 출력조건

: 첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력한다.

: 불가능할 때는 -1을 출력한다.

 

입력예시1	출력예시1
2 15 2 3	5

입력예시2	출력예시2
3 4 3 5 7	-1

 

---

🔧 아이디어

다이나믹 프로그래밍의 조건은 다음과 같다.

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

이 문제는 두 조건 모두 만족하므로 다이나믹 프로그래밍 bottom-up 방법을 통해 구현해보고자 한다.

 

1) i원일 때

i원이 주어진 화폐 가치들의 배수가 아니라면,

즉 입력 예시2경우를 보면, 4원은 3, 5, 7 중 어느 것의 배수에도 속하지 않으므로 -1을 출력했다.

 

따라서 '주어진 화폐 가치들' 의 배수가 아니라면 배열에 -1을 저장한다.

---

🔧 코드 작성

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

m_list = [0 for i in range(n)]
for i in range(n):
    m_list[i] = int(input())

answer_list = [ 10000 for i in range(10000)]
for i in range(1, target+1):
    for j in range(len(m_list)):
        if (i % m_list[j] == 0):
            answer_list[i] = min(answer_list[i], i//m_list[j])
            # 중간 점검용 출력
            # print('현재 금액 : ', i, ' | 단위 : ', m_list[j], ' | answer_list[i] : ', answer_list[i])
    if (answer_list[i] == 10000): answer_list[i] = -1

print(answer_list[target])

https://github.com/Soo-minJeon/CodingTestPractice/blob/main/study_book/ch08_DynamicProgramming/effectiveMoney.py

 

 

☺️쥔장깃헙 주소

> https://github.com/Soo-minJeon

Soo-minJeon - Overview