[백준] 11047번: 동전 0(그리디 알고리즘) - Python

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

11047번: 동전 0

 

[문제유형]

- 그리디 알고리즘

 

 

[문제]

 

[제출한 코드 및 풀이]

- 그리디 알고리즘의 대표적인 문제이고 이번 문제는 크게 어렵지 않아 일부 라인에 코드로 주석을 달아뒀다.

- 효율을 위해 moneyList를 큰 금액부터 내림차순 정렬되도록 해두고 해당 리스트를 돌면서 k의 몫과 나머지를 구해서 k가 0이 될 때까지 해당 과정을 반복했주었다.

 

n, k = map(int, input().split())

moneyList = [int(input()) for _ in range(n)] 
moneyList.sort(reverse=True)  # 내림차순 정렬

cnt = 0
for money in moneyList:
    if k >= money:            // n만큼 제시된 잔돈들을 돌면서 k가 크거나 같을 경우
        cnt += k // money     // cnt에 k를 money로 나눈 몫만 담음
        k %= money            // k를 money로 나눈 나머지를 다시 k로 바꿔줌
        if k <= 0:            // k가 0일 경우 break
            break
print(cnt)