백준 11047 동전 0 Python 3

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

11047번: 동전 0

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ11047.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
def get_minimum_cnt(N, K, coin):
    total = 0
    money = K
    for i in range(N-1, -1, -1):
        cnt = money//coin[i]
        if cnt > 0:
            total += cnt
            money %= coin[i]
            if money == 0: break
    return total

input = sys.stdin.readline
N, K = map(int, input().split())
coin = list()
for _ in range(N):
    coin.append(int(input()))
print(get_minimum_cnt(N, K, coin))

---

풀이 과정

풀이 시간 7분

 

N 종류의 동전 무한개를 가지고 K원을 만드는 가장 최소의 동전 개수를 구하는 문제이다. 거스름돈과 유사한 문제!

동전의 가치가 큰 동전부터 최대한 많이 사용하는 것이 가장 최소의 동전 개수로 K원을 만들 수 있다.

따라서, 매번 최선의 선택을 해나가면서 최적의 해를 구하는 그리디 알고리즘을 적용할 수 있다.

import sys
def get_minimum_cnt(N, K, coin):
	#총 동전의 개수
    total = 0
    #만들어야 하는 액수
    money = K
    
    #가장 가치가 큰 동전부터 차례대로 탐색한다
    for i in range(N-1, -1, -1):
        cnt = money//coin[i]
        
        #i번째 동전을 사용할 수 있는 경우,
        if cnt > 0:
            total += cnt
            #i번째 동전을 cnt개 사용하고 나서 남은 액수로 money 갱신
            money %= coin[i]
            
            #K원을 모두 만든 경우, 탐색을 종료한다
            if money == 0: break
            
    return total

input = sys.stdin.readline
N, K = map(int, input().split())
coin = list()
for _ in range(N):
    coin.append(int(input()))
print(get_minimum_cnt(N, K, coin))

#시간복잡도 = O(N) -> O(1), 공간복잡도 = O(N) -> O(1)