문제

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

풀이 아이디어

동전의 가치의 합이 k를 만들려고 하는데
k보다 큰 가치의 동전은 굳이 쓸 필요는 없다.
지금 상황에서 최선인 화폐 종류를 고르고 동전의 합을 구했기 때문에
이 부분이 '그리디 알고리즘'이 적용되었다고 볼 수 있다.

그리고 내림차순으로 정렬해 높은 금액의 동전부터 추가하며
최소 개수의 동전을 사용해 k값을 만족했다.

풀이 코드

import sys
input = sys.stdin.readline

n,k = map(int,input().split())
coins = []
for _ in range(n):
    coins.append(int(input()))
# k보다 큰 화폐는 사용하지 않는다.
coins = [coin for coin in coins if coin<=k]
coins.sort(reverse=True)
count = 0
sum = 0
for coin in coins:
    while k>sum:
        if k>=sum+coin:
            sum+=coin
            count+=1
        else:
            break
print(count)

이후에 생각난 아이디어

=> while문으로 반복해서 더하지 않고
몫 연산자와 나머지 연산자를 사용해서 while문을 반복하지 않고 빠르게 계산할 수 있다.
4=4200//1000
200=4200%1000

if k>=sum+coin:
    count+=k//coin
    k=k%coin
else:
    break

개선한 코드

import sys
input = sys.stdin.readline

n,k = map(int,input().split())
coins = []
for _ in range(n):
    coins.append(int(input()))
coins = [coin for coin in coins if coin<=k]
coins.sort(reverse=True)
count = 0
sum = 0
for coin in coins:
    while k>sum:
        if k>=sum+coin:
            count+=k//coin
            k=k%coin
        else:
            break
print(count)