[이.취.코] Chap 8. 다이나믹 프로그래밍 - 효율적인 화페 구성

@mildsalmon·2021-08-29 12:38

1. 효율적인 화페 구성

난이도
- 중
풀이 시간
- 30분
시간 제한
- 1초
메모리 제한
- 128MB

A. 문제

N가지 종류의 화폐가 있다. 화폐들의 개수를 최소한으로 이용해서 가치의 합이 M원이 되도록 만들어라. 각 화폐는 몇 개라도 사용할 수 있다.

a. 예를 들면.

2원, 3원 단위의 화폐가 있을 때 15원을 만들기 위해서는 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수다.

b. 입력 조건

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

c. 출력 조건

첫째 줄에 경우의 수 X를 출력한다.
- 불가능할 때는 -1을 출력한다.

d. 테스트 케이스

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

B. 내 답안


n, m = list(map(int, input().split()))  
n_array = []  
  
array = [0] * 10001  
  
result = 0  
  
for i in range(n):  
    n_array.append(int(input()))  
  
  
for i in range(0, min(n_array)):  
    array[i] = 0  
  
# array[min(n_array)] = 1  
  
for i in range(min(n_array), m+1):  
    # print(array)  
    for j in range(len(n_array)):  
        if j+1 >= len(n_array):  
            continue  
        if i-n_array[j+1] < 0:  
            continue  
        array[i] = min(array[i-n_array[j]], array[i-n_array[j+1]]) + 1  
print(array)  
if array[min(n_array)] == 1:  
    result = array[m]  
else:  
    result = -1  
  
print(result)  
  
# 47분 / 실패

a. 회고

풀이

반성

DP 맨 처음 문제에서 그래프 방식으로 문제를 해석해서 그래프 방식에 많이 의존했다.

결론

앞으로는 리스트를 표현할 때 사용하는 직사각형 모양으로 풀어야겠다.
이 방식도 나중가면 문제가 생길지 모르겠지만, 일단은 이런 방식으로 접근해보자.

C. 문제 해설

적은 금액부터 큰 금액까지 확인하며 차례대로 만들 수 있는 최소한의 화폐 개수를 찾으면 된다. 금액 i를 만들 수 있는 최소한의 화폐 개수는 a_i, 화폐의 단위를 k라고 했을 때 아래 점화식을 만들 수 있다. a_{i-k}는 금액 (i-k)를 만들 수 있는 최소한의 화폐 개수를 의미한다.

a_{i-k}를 만드는 방법이 존재하는 경우
- a_{i} = min(a_{i}, a_{i-k} + 1)
a_{i-k}를 만드는 방법이 존재하지 않는 경우
- a_{i} = 10001

이 점화식을 모든 화폐 단위에 대하여 차례대로 적용하면 된다. ㅅ길제로 문제를 풀기 위해서는 가장 먼저 m의 크기만큼 리스트를 할당한다. 그리고 각 인덱스를 금액으로 고려하여 메모이제이션을 진행한다.

N=3, M=7, 화폐 단위가 [2,3,5]인 경우

각 인덱스에 해당하는 값으로 10,001을 설정한다. M의 최대 크기가 10,000이므로 불가능한 수로 10,001이라는 값을 설정했으며 이보다 더 큰 수여도 상관없다. 0원일 경우 화폐를 하나도 사용하지 않았을 떄 만들 수 있으므로 값으로 0을 설정한다.
첫 번째 화폐 단위인 2부터 확인한다.
화폐 단위 3를 확인한다.
화폐 단위 5를 확인한다.