[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)은 3원짜리 동전이 있으므로 1

f(4) Math.min(f(2),f(1),f(-1))+1  즉 min(1,-1,-1)+1 인데 -1은 특수 케이스여서 제외하면 f(4)=2

f(5) Math.min(f(3),f(2),f(0))+1 min(1,1,0)+1 이므로 1

f(6) Math.min(f(4),f(3),f(1))+1 min(2,1,-1)+1 이므로 특수 케이스 제외하면 2

이렇게 f(11)까지 하면 3이 나온다.