[백준] 11047번 : 동전 0 / 그리디(Greedy) 알고리즘 / 파이썬

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

예제 입력 1 

10 4200 1 5 10 50 100 500 1000 5000 10000 50000

예제 출력 1 

6

예제 입력 2 

10 4790 1 5 10 50 100 500 1000 5000 10000 50000

 

---

 

정답

N, K = map(int, input().split())
A = []                      

A = [int(input()) for _ in range(N)]
A.reverse()
coin = 0                    

for Ai in A :
    coin += K // Ai
    K %= Ai

 

K 를 Ai 로 나누는 이유

예) K = 4200, A = [1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000]

K // Ai	K % A	coin
4200 // 50000 = 0	4200 % 50000 = 4200	0	50000원짜리 동전 0개 필요
4200 // 10000 = 0	4200 % 10000 = 4200	0	10000원짜리 동전 0개 필요
4200 // 5000 = 0	4200 % 5000 = 4200	0	5000원짜리 동전 0개 필요
4200 // 1000 = 4	4200 % 1000 = 200	4	1000원짜리 동전 4개 필요
200 // 500 = 0	200 % 500 = 200	4	500원짜리 동전 0개 필요
200 // 100 = 2	200 % 500 = 0	6	100원짜리 동전 2개 필요
0 // 50 = 0	0 % 0 = 0	6	50원짜리 동전 0개 필요
0 // 10 = 0	0 % 0 = 0	6	10원짜리 동전 0개 필요
…	…	…	…

 

 

 

오답노트

k 를 0이 될 때까지 줄여나간다 ★ 

빼기(-) 로 처리 >> 답은 맞지만 시간 초과 (Ai의 최대 입력범위가 크기 때문에 1억이 빼기로 0이 되려면 아주 오래 걸림 )

나머지 연산(%) 으로 처리를 하면 시간 초과 문제 해결 가능 (나누기로 처리를 하면 굉장히 빨라짐 )

파이썬 1초에 약 2천만번 연산 !

 

 

출처

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