[Algorithm🧬] 정올 1183 : 동전 자판기 下

문제

원래 반복문으로 작은 단위 동전부터

13 에서 3 쓰고 1원이 더 남아있으면 5 쓰고 ... 이런식으로 써보고,
13 에서 3 쓰고, 1원이 5개 미만으로 있으면 5원 쓰고, ... 이런식으로 써보고
13 에서 3 쓰고 5 쓰고 10원 쓰고.. 이런식으로 해보려고 했는데,
조건 따지기가 귀찮아서 DFS 를 이용했다.

시간초과

시간초과 때문에 check 함수를 하나 더 만들었다.

import sys
from copy import deepcopy
readl = sys.stdin.readline

def check(level, W):
    total = 0

    # 앞으로 검사할 동전을 다 합쳤을 때,
    # W 보다 작으면 검사할 필요가 없음.
    for i in range(level, 6):
        total += coins[i] * 금액[i]
    
    return total >= W
    

# 6개의 동전을 500원부터 하나씩 내려가는 것이 level
def DFS(level, W, cnt):
    global max_cnt, max_coins

    if not check(level, W):
        return

    if W < 0:
        return
    
    if W == 0:
        if max_cnt < cnt:
            max_cnt = cnt
            max_coins = deepcopy(coins)
        return

    if level == 6:
        if W == 0 and max_cnt < cnt:
            max_cnt = cnt
            max_coins = deepcopy(coins)
        return
    
        
    # 해당 동전을 몇개 사용할건지.
    for i in range(coins[level] + 1):
        if W < 금액[level] * i:
            break
        W -= i * 금액[level]
        coins[level] -= i
        DFS(level + 1, W, cnt + i)
        W += i * 금액[level]
        coins[level] += i
    


W = int(readl())
coins = list(map(int, readl().split()))
금액 = [500, 100, 50, 10, 5, 1]

max_coins = [0] * 6
max_cnt = 0
DFS(0, W, 0)
for i in range(6):
    max_coins[i] = coins[i] - max_coins[i]
print(max_cnt)
print(*max_coins)

그리디

가지고 있는 전체 금액을 다 더해놓고, (2639) 13원을 만들어야하니까
2666원을 동전을 최소로 사용해서 만들면
13원은 동전을 최대로 사용해서 만들게 됨!!

2666 // 500 = 5 >= 500원 동전 개수 4 -> 4개 사용
666 // 100 = 6 >= 100원 동전 개수 5 -> 5개 사용
166 // 50 = 3 >= 50원 동전 개수 2 -> 2개 사용
66 // 10 = 6 >= 10원 동전 개수 6 -> 6개 사용
6 // 5 = 1 < 5원 동전 개수 3 -> 1개 사용
1 // 1 = 1 -> 1 개 사용.