문제
문제의 내용은 로직을 변경하지 않는 선에서 제가 임의로 변형했습니다.
- 화폐의 종류가 다음과 같이 있습니다. 이름과 가치입니다.
- Mango : 0.01
- Banana : 0.05
- Pomegranate : 0.1
- Cherry : 0.25
- Grape : 0.5
- Apple : 1
- Lime : 2
- Orange : 5
- Kiwi : 10
- Avocado : 20
- Peach : 50
- Lemon : 100
- STDIN에서 ‘;’ 를 델리미터로 2개의 숫자를 입력받습니다. 첫번째는 물건 값, 두 번째는 손님이 지불한 돈
- 그러면 거스름돈을 어떻게 줘야할 지, 화폐의 이름의 알파벳순으로 출력해보세요
- 금액이 모자라면 ‘ERROR’라고 출력하고
- 딱 맞게 지불했으면 ‘ZERO’라고 출력합니다.
예
- 100;10
- 2.0;2
- 1.85;2
- 8.86;10
- Apple,Pomegranate,Mango,Mango,Mango,Mango
풀이 (Greedy)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| currency_prices = [1, 5, 10, 25, 50,
100, 200, 500, 1000, 2000,
5000, 10000] # normalized
currency_names = ['Mango', 'Banana', 'Pomegranate', 'Cherry', 'Grape',
'Apple', 'Lime', 'Orange', 'Kiwi', 'Avocado',
'Peach', 'Lemon']
currency_prices.reverse() # 위의 정의를 잘 못해서 그렇지.
currency_names.reverse() # 거꾸로 정의하면 여기는 필요 없습니다.
target = 123
ans = []
for i, c in enumerate(currency_prices):
if c > target:
pass
else:
d = target // c
m = target % c
for _ in range(d):
ans.append(currency_names[i])
target = target - (c * d)
print(sorted(ans))
|
아까는 잘 안풀리더니 지금은 왜 그냥 풀리지..
시간을 두고 천천히 풀었으면 풀었을 것을…
아. 이 문제를 DP로 풀려고 낑낑댔으니 그렇구나 그냥 Greedy로 풀면 되는 것을.
다음부터는 블로그 쓴다고 생각하고 풀어가야겠다.
DP 풀이
마저 DP로 그중에서도 bottom-up으로 풀어보면. 원하는 금액까지 배열을 준비하는데
dp[0] = 0
dp[1] = 1원일 때 최소 화폐
dp[2] = 2원일 때 최소 화폐
….
dp[123] = 123원일 때 최소 화폐 수
즉 dp[amount] 가 최소 화폐 수
1
2
3
4
5
6
7
| dp = [0] + [float('INF') for a in range(target)]
for c in currency_prices:
for i in range(c,target + 1): # 즉 c 가 5 이면 5원부터 6원, 7월, ...123원까지 쭉 갱신한다.
dp[i] = min(dp[i], dp[i-c] + 1)
dp[123] # 6, 즉 6개의 화폐로 돌려주면 된다. 근데 어떤 종류가 몇개인지는 안나왔네
|
덤으로 2D 배열로 하는 솔루션을 봤는데,
이건 괜히 어렵게 되어 있는 것 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| def dynamic_coin_changing(C, k):
n = len(C)
# create two-dimensional array with all zeros
dp = [[0] * (k + 1) for i in range(n + 1)]
dp[0] = [0] + [float('inf')] * k
for i in range(1, n + 1): # 1부터 7까지.
if C[i - 1] > k : # C[i - 1] 는 현재 처리하고 있는 금액
continue
for j in range(C[i - 1]):
try:
dp[i][j] = dp[i - 1][j]
except:
print(i, j)
raise ArithmeticError #현재 처리하고 있는 화폐액수보다 k 가 작으면 index error가 나버린다.
for j in range(C[i - 1], k + 1):
dp[i][j] = min(dp[i][j - C[i - 1]] + 1, dp[i - 1][j])
for i in range(1, n + 1):
print(dp[i][k])
return True
dynamic_coin_changing(list(reversed([500, 100, 50, 10, 5, 1])), 123456)
123456 # 1원으로만 했을 때 필요한 화폐 수
24692 # 1원과 5원으로 했을 때 필요한 화폐 수
12347 # 1원과 5원과 10원으로 했을 때 필요한 화폐 수
2471
1237
253
|
일부러 brute force로 풀어보면
가만, 화폐를 무한히 반복해서 사용할 수 있다고 하면, brute force로 풀 수 있나?
하나씩만 사용한다고 할 때 permute할 수 있지.. 무한히 반복해서 사용한다고 하면..
아이고. 각각의 화폐의 수를 반복사용했을 때 금액을 초과하지 않는 범위내로 퍼뮤테이션 해야할 것 같다.
머리를 써서 구할 수는 있을 것 같은데, 할 필요가 있을까.
