[백준] 11047 : 동전 0 python

 

이러한 조건이 붙어있기 때문에 이 문제는 그리디 알고리즘으로 해결할 수 있다.

큰 동전이 작은 동전들의 배수이기 때문에 큰 동전부터 사용해서 금액을 채워나가다보면 동전의 개수가 최소가 되기 때문이다.

 

 

 

1. N과 K를 입력받는다.

2. N줄에 걸쳐 입력되는 동전의 가치를 coins list에 저장한다.

3. coins 배열을 내림차순으로 정렬한다.

4. 동전의 개수를 저장할 변수 cnt를 0으로 초기화한다.

5. coins에 저장된 동전 중 값이 큰 것부터 금액 K를 맞춰간다.

    5-1. K가 각 동전(coin)보다 크다면 K를 coin으로 나눈 몫만큼 cnt를 증가시킨다.

    5-2. K를 coin으로 나눈 나머지로 K를 업데이트한다.

 

 

n,k=map(int,input().split())
coins = []
cnt = 0
for i in range(n):
    coins.append(int(input()))
coins.sort(reverse=True)

for coin in coins:
    if k>= coin:
        cnt+=k//coin
        k=k%coin
print(cnt)