11047 동전 0

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

"""
import sys
read = sys.stdin.readline

"""
동전이 N종류 있고, 동전들을 적절히 사용해서 가치의 합을 K로 만들되, 동전을 최소로 사용하자.

해법 : 큰거부터 나누자.
"""

N,K = map(int,read().split())
coins = []
for _ in range(N):
    # 코인의 개수를 줄이기 위해서 최대한 저장을 덜 하자.
    temp = int(read())
    if temp <= K :
        coins.append(temp)

num_coins = 0
coin_idx = 0
while K != 0 :
    temp_idx = -1 - coin_idx
    coin = coins[temp_idx]

    num_coins += (K // coin)
    K -= coin*(K//coin)

    coin_idx += 1
print(num_coins)

3. 풀이 및 생각

문제 풀이

이 문제는 아주 기초적인 그리디 문제다. 동전의 값이 큰 것들로 먼저 나눠보고 몫이 있으면 저장하는 식으로 진행하면 된다.

단, 나는 여기서 별로 의미는 없지만 최대한의 효율을 보장하고 싶어서 동전을 저장할 때, K를 넘는 동전은 저장하지 않기로 했다.

나의 생각

-