2294번 - 동전 2
가치가 많은 동전을 가장 많이 사용한다고 동전을 최소로 사용하는건 아닙니다.
3 24
1
7
10
입력이 이럴 때 정답은 7원 2개 10원 1개를 사용해서 3이야 하지만 이 코드대로라면 1원 4개 10원 2개를 사용해서 6을 출력합니다.
n번째 동전까지 사용했을 때 k원을 만들 때 필요한 최소 동전 수를 dp[n][k]로 두고 풀어보세요.
주어진 금액을 만들 수 없으면 -1 출력을 해야합니다(ex 2, 4, 6원 짜리론 1원을 만들 수 없다).
추가적으로 dp를 저렇게 사용한다면 굳이 동전의 크기를 소팅할 필요는 없습니다. 동전을 고르는데 순서는 중요하지 않기 때문이죠.
댓글을 작성하려면 로그인해야 합니다.
heukhyeon 6년 전