인프런 커뮤니티 질문&답변

안녕하세요 푸푸님.

주어진 문제에 따르면 3원, 5원짜리 동전이 존재합니다.

따라서, 20원을 지불하기 위해서는 15원을 지불한 뒤 5원을 추가로 사용하거나, 17원을 지불한 뒤 3원을 추가 지불하는 방법이 있습니다.

fn을 n원을 지불하기 위해 사용한 동전의 총 수라고 할 때, 위 내용을 수식으로 나타내면 아래와 같습니다.

f20 = min(f15+1, f17+1) ......(1)

여기서, f15와 f17은 base case가 아니기 때문에, 같은 방식으로 표현이 가능합니다.

f15 = min(f10+1, f12+1) ......(2)
f17 = min(f12+1, f14+1) ......(3)

여기서, 2를 1에 대입하면 아래와 같은 식이 나옵니다.

f20 = min( min(f10+1, f12+1)+1, f17+1)

말씀해주신 수식

f10+1+1, f12+1+1은 위와 같은 계산 과정에서 유도된 것으로 생각됩니다.

푸푸님이 만족하시는 답변이 되었기를 바라며, 답변 해결로 상태 변경을 부탁드립니다.

이후에도 문제를 풀거나 공부하시면서 어려운 점이 있다면 질문 올려주세요.

감사합니다.