14개의 댓글이 있습니다.
-
-
canuyes -
흠...어떻게 줄이면 될까요??ㅜㅜ
일단 이렇게는 줄여보았는데 이렇게 해도 메모리가 초과됩니다.ㅜㅜ
#include<iostream> #include<cstring> using namespace std; int N,K,COIN[100],CACHE[100][10000]; int mkCACHE(int x,int p){ if(p==0){return 1;} if(x==0){return 0;} int i,&ret=CACHE[x][p]; if(ret==-1){ 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; //system("PAUSE"); return 0; }
10년 전 link
-
-
-
canuyes -
답변감사합니다.
@일루 님의 답변을 참고하여, 재귀가 아닌 반복문으로 구현해서 해결 했습니다.
하지만, 궁금한 점이 하나 더 생겨 질문 올려봅니다 ㅜㅜ.
우선 제 코드는 아래와 같습니다.
#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; }
저는 저기서 sort아래 반복문 부분이 이해가 되지 않습니다.
저 부분이 어떻게 이뤄지는 건가요???
혹, 참고할만한 링크라도 알려주신다면 감사 하겠습니다.
10년 전 link
-
-
-
Signin -
@일루님께
제 댓글이 모호해서 죄송합니다.
제 말은 이 문제에 한해서는 map을 쓰는 것이
메모리를 줄일 수 있다는 뜻이었습니다.이 문제에서는 각 화폐(x)에 대해
1만개의 k값을 모두 쓰는 것이 아니기 때문에
계산되지 않는 금액에 대해서는 그만큼 메모리가 낭비됩니다.예를 들면 동전이 2, 4, 8원으로 3종류이고,
만들어야 하는 돈이 10원이면,
홀수 값의 k에 대해서는 메모이제이션이 불필요함에도 불구하고
2차원 배열로 캐쉬를 선언함에 의해 메모리를 낭비하게 됩니다.이 경우 캐쉬를 맵의 벡터로 선언하신 뒤,
find를 이용해서 기존에 값이 계산되어있는지를 검사하시면 될 것 같습니다.
계산이 되어 있다면 그 값을 반납하고,
계산이 되어 있지 않을 때는 주어진 k값에 대해
원소를 map에 새로 추가하는 방식으로 하시면 될 것 같습니다.코드는 아래와 같습니다.
#include <iostream> #include <cstdio> #include <vector> #include <map> #include <string> #include <algorithm> #include <cstdlib> // for atoi #include <sstream> // for stringstream #include <math.h> // for sqrt #include <string.h> // for memset using namespace std; int n, k; int coin[100]; vector<map<int, int> > cache; // 현재 사용하려는 동전이 pos, 남은 금액이 k일 때 // 주어진 동전들로 만들 수 있는 경우의 수를 ans에 추가한다. int search(int pos, int k) { if(pos == -1) { if(k == 0) return 1; return 0; } map<int, int>::iterator iter = cache[pos].find(k); if(iter != cache[pos].end()) return iter->second; int &ret = cache[pos][k]; ret = 0; int sum = 0; int maxCnt = k / coin[pos]; for(int i = 0; i <= maxCnt; i++) { sum += search(pos-1, k-i*coin[pos]); } return ret = sum; } int main(void) { scanf("%d %d", &n, &k); for(int i = 0; i < n; i++) scanf("%d", &coin[i]); sort(coin, coin+n); cache = vector<map<int, int> >(n, map<int, int>()); cout << search(n-1, k) << endl; return 0; }
10년 전 link
-
canuyes
채점 받을 수 있는 사이트의 주소는 아래와 같습니다.
문제
문제는 다음과 같습니다.
n가지 종류의 동전이 있고 그 가치는 가각 다르다.
이동전들을 적당히 사용하여 가치의 합이 k원이 되도록 하려한다.
그 경우의 수를 구하시오. ( 각각의 동전은 무제한으로 사용가능)
저는 dp의 전형적인 문제라고 생각하고
아래와 같이 풀었습니다.
그런데, 문제의 메모리 제한이 4mb로 메모리 초과가 뜨고 마네요..
문제의 크기나, 답안의 범위 (2^31)를 보았을때, int형 배열 말고는 마땅한 캐시배열이 떠오르지 않습니다.
어떻게 해결하는 것이 좋을까요?
참고로 ideone.com에서 컴파일해본 결과는 아래와 같습니다.
10년 전