글 읽기 - 인자가 2개인 점화식..

안녕하세요. 몇 일 동안 이 문제만 계속 팠는데 코드로 구현을 못하겠어서 질문드립니다.

일단 점화식이

f(n, k) = f(n - 1, k) + f(n - 1, k - D(n))

n번째까지 동전의 갯수로 k 원을 만드는 경우의 수 = n - 1번째까지의 동전의 갯수로 k원을 만드는 경우의 수 +

n - 1번째까지의 동전의 갯수로 k - D(n)원을 만드는 경우의 수

(D(n) = n번째 동전의 가치)

여기까지인 건 이해를 했습니다. 그런데 코드로 구현을 못하겠습니다.

예시로 1원, 2원, 5원이 주어졌지만, 1원, 3원이 주어졌을 때의 경우를 생각해보니 머리가 아프더라구요...

위의 점화식을 바탕으로 어떻게 코드로 구현을 할 수 있을까요?

점화식이 틀린것 같네요.

f(n, k) = f(n - 1, k) + f(n , k - D(n))

n과 n-1이 1차이이기 때문에 아래 처럼 구현 가능합니다.

for (i = 0; i < N; i++) {
  for (j = coin[i]; j <= K; j++) {
   c[j] += c[j - coin[i]];
  }

}

n과 n - 1이 1차이기 때문에 구현 가능하다는 말이 무슨 뜻인가요?

죄송하지만 c[j] += c[j - coin[i]]; 가 의미하는 바를 설명해주실 수 있나요...?

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

Baekjoon Online Judge