백준 알고리즘 11047 (동전 0) - python

백준 알고리즘 11047 (동전 0) - python
> https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

주어지는 최소의 동전으로 조합하여 값을 맞추는 문제.

그리디하게 큰 수부터 접근하면 된다.

각 동전의 수는 무수히 많으므로 나눠서 몫을 이용한다.

 

[문제 풀이]

1. 큰 수부터 접근하기 편하도록 배열 reverse

  -> 속도가 중요하다면 N-1번째부터 반대로 접근하는 것이 좋을 듯.

2. 몫을 구해서 최대 중복 코인 값을 알아낸다.

3. 목표 금액에서 빼면서 카운트한다.

4. 맞추면 바로 끝낸다.

 

import sys
N, M = map(int, sys.stdin.readline().split())

coins = [int(sys.stdin.readline().rstrip()) for _ in range(N)]
coins.reverse()
cnt = 0
for coin in coins:
    _div = M // coin  # 최대 중복 코인
    if _div > 0:
        M -= (_div * coin)  # 목표 금액에서 빼고
        cnt += _div  # 갯수 카운트
    elif M == 0:  # 맞추면 끝
        break
print(cnt)