11047, Silver 2

백준 2021. 8. 19. 14:58

11047번: 동전 0

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

www.acmicpc.net

문제

$n(1 \leq n \leq 10)$ 종류의 동전$c_{1},\ c_{2},\ \cdot \cdot \cdot,\ c_{n}(c_{i}\mid c_{i+1})$이 주어진다
이 동전들로 $k$원을 내기 위한 최소 개수를 구하라(돈을 못 내는 경우는 존재하지 않는다)

Greedy
단위가 큰 동전을 우선으로 가능한 많은 돈을 낸다

Claim