DP의 대표적인 동전문제 관련질문입니다.
글쓴이: canuyes / 작성시간: 일, 2013/07/28 - 10:00오후
우선 문제는 아래와 같습니다.
n가지 종류의 동전이 있고 그 가치는 가각 다르다.
이동전들을 적당히 사용하여 가치의 합이 k원이 되도록 하려한다.
그 경우의 수를 구하시오. ( 각각의 동전은 무제한으로 사용가능)
저는 전형적인 DP문제라고 생각하고 다음과 같이 작성하였습니다.
#include<iostream>
#include<cstring>
using namespace std;
int N,K,COIN[100],CACHE[101][10001];
int mkCACHE(int x,int p){
int i,&ret=CACHE[x][p];
if(ret==-1){
if(p==0){ret=1;}
else if(x==0){ret=0;}
else{
ret=0;
for(i=0;p-COIN[x-1]*i>=0;i++){ret+=mkCACHE(x-1,p-COIN[x-1]*i);}
}}
return ret;
}
int main(void){
int i;
cin>>N>>K;
for(i=0;i<=N;i++){memset(CACHE[i],-1,sizeof(int)*(K+1));}
for(i=0;i<N;i++){cin>>COIN[i];}
cout<<mkCACHE(N,K)<<endl;
return 0;
}하지만 문제의 메모리 제한이 4mb였기 때문에 캐시배열로 인해 메모리 초과를 경험하였습니다.
그래서 재귀를 사용하지 않는 형식으로 아래와 같은 반복문코드(배열 역시 재활용하는)을 작성하여서 답을 얻었습니다.
#include<iostream>
#include<cstring>
using namespace std;
int N,K,COIN[100],CACHE[2][10001];
int mkCACHE(void){
int i,j,k;
for(i=0;i<=N;i++){
for(j=0;j<=K;j++){
if(j==0){CACHE[0][j]=1;CACHE[1][j]=1;}
else if(i==0){CACHE[0][j]=0;}
else{
CACHE[1][j]=0;
for(k=0;j-COIN[i-1]*k>=0;k++){CACHE[1][j]+=CACHE[0][j-COIN[i-1]*k];}
}}
if(i!=0){memcpy(CACHE[0],CACHE[1],sizeof(int)*(K+1));}
}
if(N==0){return CACHE[0][K];}
return CACHE[1][K];
}
int main(void){
cin>>N>>K;
for(int i=0;i<N;i++){cin>>COIN[i];}
cout<<mkCACHE()<<endl;
return 0;
}온라인 저지이다 보니 다른 분들의 답안을 볼 수 있었습니다.
하지만 그 코드를 이해할 수 없었습니다.
그 코드에 관해 질문올립니다.
그 코드는 아래와 같습니다.
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
int i,j,n,k,a[101]={0,};
int d[10001]={0,};
scanf("%d %d",&n,&k);
if(n<1 || n>100 || k<1 || k>10000) return 0;
for(i=0;i<n;i++) scanf("%d",&a[i]);
d[0]=1;
sort(a,a+n);
for(i=0;i<n;i++){
for(j=a[i];j<=k;j++){
d[j]+=d[j-a[i]];
}
}
printf("%d\n",d[k]);
return 0;
}아무래도 중요한부분은 이중for문 부분인 것 같습니다.
저 이중 for문의 의미를 알려주세요.
겸손한 마음으로 답변 기다립니다.
Forums:
// d[X] : X원을 만드는 경우의
// d[X] : X원을 만드는 경우의 수 d[0] = 1; // 0원을 만드는 경우의 수는 1가지. // 동전이 1가지만 있을때 (가치는 a[0]원), N*a[0]원을 만드는 경우는 1가지이고, 나머지 액수의 경우는 0가지 // 이것이 i=0 일때의 for 루프가 하는 일 d[ a[i]의 배수 ] = 1; // i=1 부터는 a[i]원짜리 동전이 추가되었을 때 j 원을 만드는 경우의 수 d[j] = a[i]원짜리 동전이 추가되기 전에 계산한 d[j] + a[i]원짜리 동전이 추가된 후에 j-a[i]원을 만드는 경우의 수 (여기에 a[i]원 동전 하나를 더하면 j원이 됨)예를 들어서
1원짜리와 5원짜리를 가지고 10원을 만든다면
액수: 0 1 2 3 4 5 6 7 8 9 10 1원짜리사용: 1 1 1 1 1 1 1 1 1 1 1 5원짜리추가: 1 5원을 만들때 5원짜리를 쓰는 경우가 추가 1 6원도 마찬가지 1 7원도 마찬가지 ... 2 5원을 만드는 경우의 수 2가지(1*5, 5*1)에서 5원짜리를 하나 추가해서 10원을 만드는 2가지 d[10] = 1 + 2 = 3이런 식인 거죠.
물론 이건 코드를 보면서 역으로 생각한 거고... 대뜸 풀라고 하면 금방 떠올릴 수 있었을지는 자신이 없네요 ^^;
좋은 하루 되세요!
댓글 달기