[백준] 11047번

11047번 동전 문제에 대한 설명

이번 문제도 알고리즘을 생각하고 풀면 간단하게 풀 수 있는 문제였다.

입력 첫째 줄에 동전의 개수와 원하고자 하는 최솟값을 입력하여 그에 따른 최소 동전 개수를 구하는 문제였는데,

리스트에 차곡차곡 쌓아주고, 내림차순으로 거꾸로 정렬시켜 a % b 를 했을 때, b가 더 큰 수라면 a가 그대로 출력되지 않을 경우를 조건으로 이용하여, 풀이를 하였다. 그러면 그 조건에 해당하는 동전의 종류만이 계산이 되어진다. 파이썬으로 풀이한 과정은 다음과 같다.

 

coin, money = map(int, input().split())
num = []

for i in range (coin):
    num.append(int(input()))

num.sort(reverse=True)
result = 0

for i in range (len(num)):
   if (money % num[i] != money):
       result += money // num[i]
       money = money % num[i]
print(result)