본문 바로가기

728x90

최소동전개수1

[DP기초] 필요한 동전의 최소개수 구하기 2원,3원,5원의 동전이 있고 이 동전들을 조합해서 최소개수로 그 합이 11이 나오게 해보자. 5원x1+3원x2+2원x0 =11 -->3 5x1 + 3x0 + 2x3 =11 -->4 5x0 + 3x1 + 2x4 =11 -->5 5x0 + 3x3 + 2x1 =11 -->4 그러면 최소개수는 3이다. f(11)의 경우 11에서 2를 뺀 f(9) 11에서 3을 뺀 f(8) 11에서 5를 뺀 f(6) 으로 subproblem들을 나눌 수 있다. f(11)=Math.min(f(9),f(8),f(6))+1 이것을 일반화하면 f(n)=Math.min(f(n-2),f(n-3),f(n-5))+1 f(0)=0 f(1)은 1원짜리 동전이 없으므로 특수 케이스이기 때문에 -1 f(2)는 2원짜리 동전이 있으므로 1 f(3)은.. 2021. 8. 6.

이전 1 다음

728x90

티스토리툴바