유에스비 어딨니?

생각금액이 다른 동전 N개와 원하는 금액 K가 주어진다. N개의 동전들을 최소한으로 사용하여 K를 만들 때 그 최소한의 동전수를 출력하여라. 만들 수 없을 경우 -1을 출력한다. 처음 생각DFS를 통해 풀이를 하였으나 시간 초과가 나왔다. 다음 생각이런 동전류의 문제는 이전 값을 계산해서 나아가는 다이나믹 프로그래밍(DP) 방식을 사용해서 푸는 경우가 많으므로 DP로 접근하였다. 다다음 생각동전의 숫자를 구하는 것이므로 이 금액을 만들 수 있나의 개수를 파악하면서 가는것이 아닌 이 금액을 몇 개의 동전으로 만들 수 있나를 파악하면서 가도록 진행하였다. 자세한 설명은 코드상에 주석으로 달아 놓았습니다.다다다음 생각따라서 DP를 구하기에 앞서 DP에 해당 Index 1~K 일 때, 주어진 동전의 배수를 미리..