3개의 댓글이 있습니다.
-
-
riceluxs1t -
c(n-m, m) 은 해당 m번째 동전을 1개만 넣은 경우의수가 아니라. 정의하신 바와 같이 n-m의 금액을 m번째 동전 종류까지 사용해서 만들수 있는 경우의 수 입니다.
9년 전 link
-
-
-
riceluxs1t -
c(n, m)은 n의 금액을 m 번째 동전 종류까지 사용하여 만들수 있는 경우의수라 하면
c(n, m) = c(n, m-1) (m번째는 한번도 안쓴경우) + c(n- value[m], m)은 m을 일단 한번 '이상'은 사용한 경우 입니다.
전체집합 = m 한번도 안쓴경우 + m을 한번이상은 쓴경우.
9년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
kdh9520
1 ~ nowItem까지의 동전종류를 사용해서 nowMoney를 나눠줄 수 있는 경우의 수를 반환하는 함수를
private static int C(int nowMoney, int nowItem) {}
라고 할 경우 재귀함수를 짤 때 점화식이
m개의 어떤 동전으로 n원을 거스를 수 있는 경우의수(C(n, m))는 그 동전을 사용하지 않고 전부 거스를 수 있었던 수(C(n,m-1)) + 그 동전을 무조건 사용한 경우의 수이다.
여기서 그 동전을 사용하지 않고 전부 거스를 수 있었던 수는 C(n, m-1)은 당연히 이해가 가는데
왜 그 동전을 무조건 사용한 경우의 수가 C(n - m의값, m)인지 이해가 가지 않습니다.
C(n - m의값, m)은 해당 m번째 동전을 1개만 넣은 경우의수가 아닌가요??
C(n - m의값 - m의값, m)이 m번째 동전을 2개 넣은 경우의수가 되고 이런식 아닌가요???
이틀동안 계속 생각해봐도 왜 이런 점화식이 성립하게 되는지 이해를 못하겠네요 ㅜㅜ 설명좀 부탁드려요..
9년 전