[백준 11047 : PYTHON] 동전 0

문제 풀기 : 11047번

11047번: 동전 0

문제

준규가 가지고 있는 동전은 총 N종류이다(각각의 동전을 매우 많이 가지고 있다.)

동전을 적절히 사용해서 동전의 합을 K로 만들려고 한다.

이 때 필요한 동전 개수의 최솟값을 구한다.

문제풀이

최적의 해를 구하는 그리디 문제이다.

동전의 합을 크게 만들기 위해선 동전의 종류 중 가치가 큰 동전의 필요한 개수부터 빼나가면 된다.

전체코드

# n : 동전의 종류 수, k : 만들려는 가치의 합
n, k = map(int, input().split())

# 동전의 종류를 담을 배열
coins= []
for i in range(n):
    coins.append(int(input()))

# 내림차순으로 정렬
coins.sort(reverse=True)

count = 0
for coin in coins:
    # 해당 동전의 최대 개수 계산
    count += k // coin
    k = k % coin

print(count)