kioio5   2달 전

점화식이 C[c,m] = C[c-1,m] + C[c,m-D(c)] 라고들 하시는데

1. 도출하는 과정을 알고 싶습니다.

2. C[c,m-D(c)]가 의미하는 것을 알고싶습니다.

초보자니 고수님들이 자세히 설명해주시면 감사하곘습니다.

oyj0594   2달 전

고수는 아니지만 DP 점화식을 세울 때는 구하고자 하는 것을 잘 '정의' 하는게 중요합니다.
C[c,m] = C[c-D[m] , m] + C[c, m-1] 
C[c,m] 이라는 구하고자 하는 값은 c (cost) 를 m (동전 종류를 배열에 입력했을 경우 몇 번째 동전까지 사용할 것인지) , 이 두 변수로서 정의합니다.

1000원을 만들어야하고 동전은 100원 500원이 있을 때, c = 1000원 이고 m은 1이 되겠죠. (0 - 100원, 1 - 500원)
그렇다면 m번째 동전까지 이용해서 c원을 만드는 경우의 수는 

m번 째 동전하나를 사용을 하고 c - D[m] ( 1000원 - 500원) 을 m번 째 동전까지 이용해서  만드는 방법 (동전은 여러번 사용가능하다는 전제입니다.)
m번 째 동전을 아예 사용하지 않고, c원을 m-1번째 동전까지만으로 만드는 방법

의 합이라고 정의할 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.