[백준][11047] 동전 0 | 파이썬 | 그리디(Greedy)

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

 

👉 문제 분석

동전의 종류는 총 N종류(각각의 동전을 많이 가지고 있음).

적절히사용하여 가치의 합을 k로 만들려고 한다.

이때 필요한 동전 개수의 최솟값

 

👉 알고리즘 설계

1. 동전의 종류와 만들고자하는 합을 입력받는다.
2. 동전의 가치들을 리스트로 만들어주고 내림차순으로 바꿔준다.
3. 동전의 갯수를 담아줄 변수 하나를 만들어주고 리스트의 가장 큰 값으로 나눈 몫을 그 변수에 담아준다.
4. 이를 리스트의 크기순으로 반복한다.
5. 이때 남은 수는 리스트안의 값으로 나눈 나머지값이 된다.

👉 코드

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

money = []
for _ in range(n):
    money.append(int(input()))

money.reverse()  #  내림차순 

money_number = 0
for i in money:
    money_number += (k//i)  #  몫(동전의 갯수)을 money_number에 넣어준다
    k %= i  #  나머지 남겨준다
print(money_number)

 

👉 시간복잡도

O(N)