효율적인 화폐 구성 226p 점화식 질문

[zi-gae]

a_i-k 는 금액 (i - k) 를 만들 수 있는 최소한의 화폐 개수를 의마한다고 하셨는데 왜 이렇게 되는지 모르습니다 ㅠ 다른 dp 문제도 그렇고 점화식을 보고 코드를 짜는건 문제가 없는데 a_i = min(a_i, a_i-k + 1) 라는 점화식을 유도하는 과정이 궁금합니다. 이러한 문제를 접했을때 점화식을 얻는 팁이 있을까요?

[ndb796]

안녕하세요, @devGW 님.

좋은 질문 감사합니다.

이 유형은 배낭 문제 등 다른 다이나믹 프로그래밍에서 사용되는 아이디어와 유사한 구조를 가지고 있습니다. 처음에는 어렵게 느껴질 수 있으나, 한 번 익숙해지시면 보다 수월하게 해결할 수 있을 겁니다.

해당 문제에서 (i - k)를 만들 수 있는 최소한의 화폐 개수를 고려해야 하는 이유는, 우리가 (i - k) 원을 만들 수 있다면, 거기에 k 원을 더하면 i 원도 만들 수 있기 때문입니다.

해당 문제 풀이는 유튜브에 강의로 올라와 있으므로 한 번 확인해보시면 도움이 될 것 같습니다. (이코테 2021) 다이나믹 프로그래밍 43분 20초가량에서 해당 문제 해설을 진행합니다.

감사합니다. 나동빈 드림