그리디 | 백준 11047 동전 0

문제

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

동전을 N종류 가지고 있고 각각의 동전의 개수는 무한할 때, K원을 만들기 위해 필요한 동전 개수의 최솟값을 구해라

 

입력

• 첫째 줄: N과 K
• 둘째 줄~ : N개의 줄에 동전의 가치가 오름차순으로 주어짐

 

출력

• K원을 만들기 위해 필요한 동전 개수의 최솟값

그리디

 

그리디는 현재의 순간의 최적의 선택을 하면 전체적으로 최선임을 가정하는 알고리즘.

예를 들어 거스름돈은 가장 큰 단위의 동전부터, 회의실 배정은 가장 빨리 끝나는 회의부터.

 

다만 이 가정이 늘 참이 되는 것이 아님에 주의.

아래와 같은 조건을 만족해야 한다.

 

1. 각 단계에서의 최적 선택이 전체 최적 선택의 일부여야 한다.

2. 문제를 부분 문제로 해결할 수 있으며, 부분 문제의 최적해들이 전체 최적해를 구성해야 한다.

e.g.) 최단 경로 문제에서 현재까지의 최단 경로가 전체 최단 경로의 일부인 경우

 

 

풀이

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
coins = [int(input().strip()) for _ in range(N)]
result = 0

for i in range(N):
    q = K//coins[N-i-1]
    if q > 0:
        result += q
        K -= (q*coins[N-i-1])
    if K == 0:
        break

print(result)

 

1. 동전의 가치를 하나의 배열에 오름차순으로 넣고

2. 뒤에서부터 해당 값으로 K를 나눈다.

3. 몫이 발생하면 result에 더하고 몫*가치만큼을 K원에서 뺀다.

4. K == 0 or 동전 배열을 모두 돌면 끝남.