fineman91   7달 전

D(n, k) : n가지의 동전으로 k원을 만들 수 있는 경우의 수

n가지의 동전으로 k원을 만들기 위해서

(1) Cn 동전을 쓰지 않고 k원을 만든 경우 : N(n-1, k)

(2) Cn 동전을 1개라도 써서 k원을 만든 경우 : N(n, k-Cn)

D(n, k) = (1) + (2) = D(n-1, k) + D(n, k-Cn)

가 도출된다고 하는데.. (2)번 과정이 이해가 안가네요. 고수님들 설명좀 부탁드려요~

chatterboy   7달 전

이 문제에서는 같은 종류의 동전을 몇 번을 사용해도 상관없다고 했기 때문에 n번째 동전을 한번 사용했다는 상태를 나타낸 거에요.

만약, 최대 한번 사용가능하다고 하면, D(n,k) = D(n-1,k) + D(n-1,k-Cn) 이 되겠져

fineman91   7달 전

음.. 그렇다면 n번째 동전이 한 번 사용된 것이 아니라 여러번 사용된 경우는 또 처리를 해줘야하나요..?

chatterboy   7달 전

D(n,k) = D(n-1,k) + D(n,k-Cn)이 여러번 처리를 해줄 수 있어요.

D(n,k) -> D(n,k-Cn) -> D(n, k-Cn-Cn) -> D(n, k-Cn-Cn-Cn) ... n번째를 더 이상 사용하지 않는 경우는

-> D(n-1, k-Cn-Cn-Cn) 으로 나타날수 있어여

fineman91   7달 전

아무래도 점화식 도출 과정 전체를 제가 이해하지 못하고 있는것 같은데.. 전체적으로 점화식 도출에 대해 기준과 과정 설명 뷰탁드려요 될까요?ㅠㅠ

fineman91   7달 전

아 혹시 D(n, k)의 정의를 해석할 때,

n가지의 동전을 사용해서 k원을 만드는 경우의 수 보다는

"1번~n번 동전을 사용해서 k원을 만드는 경우의 수"

로 해석해야 더 바람직한(이해하기 쉬운)건가요..?

D(n-1, k) : 1번~n-1번 동전을 사용해서 k원을 만드는 경우

D(n, k-Cn) : 1번~n번 동전을 사용해서 k-Cn원을 만드는 경우

chatterboy   7달 전

네 그렇게 이해하시면 됩니다 !

fineman91   7달 전

아아...... 감사합니다.

다시 도전중입니다. 감사해요^^

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