[백준 2294] 동전 2

https://www.acmicpc.net/problem/2294 문제이해 n 가지 종류의 동전을 활용해 주어지는 k를 완성하면 된다. 사용한 동전의 개수가 최소가 되도록 해야 한다.

풀이 첫 번째 접근으로 가장 단위가 높은 동전부터 사용하는 그리디 방법을 사용했다. 단순한 예제에서는 잘 작동을 했지만 복잡한 반례 반례 1 반례 2 8 7804 6531 5312 4188 903 458 310 272 97 3 1203 63 72 888 에서 최적의 정답뿐만 아니라 최적이 아닌 해도 찾지 못했다.

그 이유는 무조건 높은 단위의 동전을 먼저 사용하는 그리디의 방식으로는 작은 단위의 동전을 더 많이 사용해야 하는 경우의 수를 찾지 못하기 때문이다. 인터넷에서 DP로 풀어야 한다는 정보를 얻어서 백준 2293번과 같이 DP로 접근해 봤다.

동전의 순서가 1, 2, 3의 순서로 주어지는 경우를 분석했을 때 DP[j] = DP[j-i] + 1의 점화식을 얻을 수 있었다. 그러나 통과를 하지 못했...