[백준] 11047번 동전0 (Python)

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

11047번: 동전 0

---

풀이과정

①문제 바라보기

기본적인 그리디 문제다.

어렵게 낼 수 있다면 굉장히 어렵게 낼 수 있는 문제인데 이 문제의 경우에는 굉장히 기본기본기본적인 문제같다.

 

②아이디어 펼치기

연산자 %와 //을 활용하면 간단히 풀릴 것이다.

몫을 구해서 만약 1 이상이라면 남는 돈은 %한 값이 되는거고 빠져나간 동전의 개수는 //가 되는 것이다.

이때 필요한 동전의 개수를 cnt에 더해주면 된다.

 

③최종코드

import sys

N, K = map(int,sys.stdin.readline().rstrip().split())
coin_type = list()
for _ in range(N):
    coin_type.append(int(sys.stdin.readline().rstrip()))

coin_type.sort()
coin_type.reverse()
ans = 0
for coin in coin_type:
    tmp = K//coin
    ans += tmp
    K = K%coin

print(ans)