둔필승총

www.acmicpc.net/problem/11047

문제

준규가 가지고 있는 동전은 총 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

예제 출력 2

12

[문제 해설]

n종류의 동전으로 k금액을 만들면 된다. 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제로 간단한 아이디어만 떠올릴 수 있으면 된다. 그것은 바로 '가장 큰 화폐 단위부터' 나누어 주는 것이다. 물론 k보다 큰 금액이면 나눌 수 없으므로 k보다 작은 것중에 제일 큰 수부터 나누면 된다.

n,k=map(int,input().split())
a=[]
for _ in range(n):
    a.append(int(input()))
a.sort(reverse=True)
ans=0
for i in range(n):
    if a[i]>k:
        continue
    else:
        ans+=k//a[i]
        k=k%a[i]
print(ans)

그리디 알고리즘은 모든 알고리즘 문제에 적용할 수 있는 것은 아니다. 대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 많다. 

사실 그냥 머리에 떠올린대로 그리디 해법을 생각했을때 해법이 정당한지 컴토해야 한다. 여기서 그리디 알고리즘을 검증하려면 조건을 유심히 봐야된다.

 괄호 안에 주어진 조건을 자세히 살펴보자. 이 문제에서는 조건이 중요하다.

(1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) Ai는 Ai-1의 배수라는 점. 그리디 알고리즘의 정당성을 부여하려면 예시를 들어보자. 만약 k의 값이 800원이고 Ai 배열에서 500원, 400원, 100원이라면 우리가 짠 그리디 알고리즘으로는 500원 1개, 100원 3개가 최적의 답으로 나온다. 그러나 사실 400원 2개 주는 것이 더 이득이다. 이 문제는 다이나믹 알고리즘으로 따로 풀 수 있다.

 이 문제에서 그리디 알고리즘을 쓸 수 있었던것은 Ai는 Ai-1의 배수라는 사실 때문이다.

아래에서 더 자세히 설명해 두었다.

2020.10.02 - [알고리즘/알고리즘 이론] - 그리디(Greedy) 알고리즘