백준 10047번: 동전 0

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

문제 접근

동전의 종류 N개, 목표 합을 K
로 첫째 줄에 입력받았을 때,
목표 합 K에 도달하는 동전의 최소개수를 구하는 문제.

동전의 값을 내림차순으로 정렬하여
큰 값부터 K를 나누어 몫을 개수에 더하고
나머지를 다시 K로 갱신하여 반복하여 풀었다.

해답 및 풀이

from sys

coin = []
count = 0

N, K = map(int,sys.stdin.readline().split())

for i in range(N): #N개만큼 동전의 가치 입력
    coin.append(int(sys.stdin.readline()))

coin.sort(reverse=True) # 내림차순 정렬

for value in coin:
    count = count + (K//value) # 필요한 코인수 count
    K = K % value # 쓰고 남은 돈 
    if(K <=0):
        break

print(count)