먼저 1원만 써서 만들수 있는 경우의 수를 찾습니다. 1원으로 0~10원을 만드는 경우는 각각 한 가지 밖에 없죠.
A0 = 1, A1 = 1, A2 = 1, A3 = 1, A4 = 1, A5 = 1, A6 = 1, ..., A10 = 1
그 다음 2원이 추가됐을 때 경우를 셉니다.
A0 = 1, A1 = 1, A2 = 2, A3 = 2, A4 = 3, A5 = 3, A6 = 4, ..., A10 = ?
규칙을 찾으셨나요?
2원이 추가됐을 때 An = An + An-2 입니다.
예를 들어 A2를 구성하는 경우는 1+1 (1로만 구성된 A2)과 0+2 (A0에 2를 더한 경우, 즉 적어도 2원을 한 번 쓴 경우) 두 가지 입니다.
A3을 구성하는 경우: 2가지
A3: 1+1+1 (1원으로만 구성)
A1+2: 1+2 (적어도 2원을 한 번 쓴 경우)
A4을 구성하는 경우: 3가지
A4: 1+1+1+1
A2+2: 1+1+2, 0+2+2
5원이 추가된 경우도 마찬가지로 진행됩니다.
shoeskwang 7년 전
안녕하세요.
2293 동전 문제 DP로 풀어보고 싶어서
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
if(A[i]<=j){
dp[j]+= dp[j-A[i]];
}
}
}
System.out.println(dp[k]);
이런 소스를 구해서 돌려봤는데요.
처음부터 차근차근히 설명이 나와있는 곳이 없어서 잘 이해가 가지 않습니다.
분할정복을 사용한다는거도 같고..
동적계획법에 대해서 잘 모르는데
소스를 돌려봐서 전체 동전 갯수를 증가시키면서? 하는거 같던데..
dp[j]+= dp[j-A[i]]; 라는 식이 나오기까지의 과정을 알 수 있을까요?
기초적인것부터 알수 있는 사이트나 설명 해주시면 정말 감사하겠습니다.