[백준 02294] 동전 2 [Java]

문제

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

---

풀이

N가지 종류의 동전이 주어질 때, 동전의 합이 K가 되는 최소 개수를 구하는 문제다.

N은 최대 100이므로, 모든 동전에 대해 K를 만들어보는 경우를 전부 계산해볼 수 있다.

dp[i] : 현재까지 살펴본 동전들로 i원을 만들기 위한 최소 개수

우선 K의 최대는 10,000이므로 dp를 10,001, dp[0] = 0으로 초기화하자.

이제 입력받은 동전에 대해 최소 동전 개수를 갱신하면 된다.

범위 coin ~ K에 대해 현재 동전의 액수를 뺀 기록( dp[i - coin] )에 현재 동전 더하는 수가 적은 경우로 갱신해주면 된다. 

만약 dp[K]가 초기값인 10,001이라면 K를 만드는 경우의 수가 존재하지 않는 경우이므로 -1을 출력하자

---

소스코드

보기