문제

' 11047번 동전 0 '
https://www.acmicpc.net/problem/1436

풀이

조건

• 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 즉, 금액이 가지고 있는 동전보다 클 경우 계속해서 뺄 수 있다.
• 동전의 가치는 오름차순으로 주어진다.
• K원을 만드는데 필요한 최소 동전 개수를 출력한다.

풀이 순서

• 동전의 종류 N과 만들어야 되는 값 K원을 입력받고 이후 N개의 줄에 동전의 가치를 오름차순으로 입력받는다.
• 최소 동전 개수를 세아릴 변수와 함수를 작성한다. 이떄, 최소 동전 개수를 구해야 하므로 가장 큰 값부터 최대한 많이 사용할 수 있도록 함수를 작성한다.

코드

Python

def func(K):
    global total
    tmp = []
    for i in range(N)[::-1]:  # 숫자가 큰 것부터 비교해서
        if len(str(K)) >= len(str(arr[i])):  # 단위가 K 이하는 다 리스트에 저장
            tmp.append(arr[i])
    idx = 0
    while K > 0:
        if K == 0:
            return
        elif K >= tmp[idx]:  # 단위 큰 것부터 뺄 수 있을 때 까지 빼기
            K -= tmp[idx]
            total += 1
        else:
            idx += 1


N, K = map(int, input().split())
arr = [int(input()) for _ in range(N)]  # 동전의 가치 (오름차순)
total = 0  # 필요한 동전 갯수
func(K)  # 함수호출
print(total)

다른 방법

N, K = map(int, input().split())
lst = []
total = 0

for i in range(N):
    lst.append(int(input()))  # [50000,10000,5000,1000,500,100,50,10,5,1]

for i in range(N)[::-1]:
    if K - lst[i] >= 0:
        total += K // lst[i]  # 몫 만큼 빼준다.
        K = K % lst[i]  # 나머지가 K가 된다.
    if K == 0: # 0이되면 멈춘다.
        break

print(total)