[백준/Python] 11047. 동전 0

https://www.acmicpc.net/problem/11047

 

 

풀이 

 

동전 구하기는 그리디 알고리즘에서 유명한 문제이다. 

 

해당 문제에서 내림차순으로 정렬해 나누기를 반복했을 때 정답이 될 수 있는 이유는 arr 값들끼리 배수의 관계에 있기 때문이다. 

 

만약 arr = [100, 400, 500, 100] 인데, 800원을 만들 수 있는 동전의 최소 개수는 

아래의 코드 기반으로 하면 4개가 된다. (500원 1개, 100원 3개) 

하지만 이론 상으로는 400원 2개로 끝이 난다. 

 

따라서, 그리디 문제를 풀 때는 

1. 완전탐색을 고민해보고 

2. 반례가 없는지 꼭 확인해봐야 한다. 

 

N, K = map(int, input().split())

arr = []
for _ in range(N):
    arr.append(int(input()))
arr.sort(reverse=True)
ans = 0
for val in arr:
    if K == 0:
        break
    if K < val:
        continue
    else:
        ans = ans + K // val
        K = K % val
print(ans)