posts/2021-08-04-%EB%B0%B1%EC%A4%80-1398-%EB%8F%99%EC%A0%84-%EB%AC%B8%EC%A0%9C/

[utterances-bot]

家庭宽带配置2 :: 개발 일기장

최소 동전의 수를 묻는 문제입니다.
주어진 동전들이 Canonical 하다면 그리디하게 풀 수 있습니다. 이 문제에서는 그렇지 않으므로 DP를 이용해서 풀어야합니다. 일반적으로 주어진 금액의 크기만큼 배열크기를 선언하지만 이 문제에서는 금액의 크기가 $10^{15}$이므로 배열선언도 어렵습니다.
하지만 동전들을 3개씩 나누어 본다면 배수관계를 만족함을 알 수 있습니다.
즉 DP를 100씩 끊어서 사용하면 됩니다.
코드 #include <bits/stdc++.h> #defi

http://localhost:1313/posts/2021-08-04-%EB%B0%B1%EC%A4%80-1398-%EB%8F%99%EC%A0%84-%EB%AC%B8%EC%A0%9C/