글 읽기 - 'DP와 함께하는 알파벳공부' D 번-동전1 문제 질문좀하겠습니다.

sgc109 8년 전 0

동전의 단위를 입력받아 내림차순 정렬을 하고 큰 단위의 동전부터 최대 사용가능 개수부터 0개까지 하나씩줄여가며 그 아래 단위에도 재귀적으로 조합하여 가장 마지막 단위까지 도달했을때 합이 만들고자하는 금액 k 와 같다면 세는 식으로 해서 계산하게했고

D(i,j) = 현재까지 i원을 만들었고 개수를 정해야하는 단위가 coin[j] 일때 최종금액 k를 만드는것이 가능한 경우의 수

로 하여 계산을 하고자했는데 메모리제한이 4MB 인데 unsigned int dp[10000][100] 만 해도 4MB 가 되어 메모리 초과가 뜹니다.. 어떻게 개선하면 좋을까요?

@hongjun7

#define REP(i,a,b) for(int i = a; i < b;++i)
#define FOR(i,n) REP(i,0,n)

#include<iostream>
#include<vector>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<math.h>


using namespace std;

int n,k;
int coin[101];
unsigned int dp[10001][101];

unsigned int solve(int sum, int i) {
	if (sum > k) return 0;
	if (i == n) return (sum == k);
	if (i == n - 1) return ((k-sum)%coin[i] == 0);
	unsigned int cnt = 0;

	int rep = k / coin[i];
	FOR(j, rep+1) {
		if (dp[sum + j*coin[i]][i + 1] != -1) cnt += dp[sum + j*coin[i]][i + 1];
		else {
			unsigned int tmp = solve(sum + j*coin[i], i + 1);
			dp[sum + j*coin[i]][i + 1] = tmp;
			cnt += tmp;
		}
	}
	return cnt;
}


int main() {
	cin >> n >> k;
	FOR(i, n) {
		scanf("%d", &coin[i]);
	}

	FOR(i, 10001) {
		FOR(j, 100) {
			dp[i][j] = -1;
		}
	}
	FOR(i, n) {
		REP(j, i+1,n) {
			if (coin[i] < coin[j]) {
				int tmp = coin[i];
				coin[i] = coin[j];
				coin[j] = tmp;
			}
		}
	}

	cout << solve(0, 0) << endl;

	return 0;
}

nosqeil24 8년 전 1

dp[k][i] 를 채우기 위해서는 dp[k'][i-1] (0<=k'<=k)의 값이 필요합니다.

즉, dp[k][i] 를 채우기 위해서 dp[k'][0~i-2] 에 있는 값은 필요가 없다는 사실을 이용하여

다이나믹 배열을 모듈라 연산을 통해 dp[10001][2] 로 줄일 수 있습니다.

dp[i][k] = sum(dp[i-1][k') <=> dp[i%2][k] = sum(dp[(i-1)%2][k'] (모듈라 연산 이용)

슬라이딩 윈도우 기법으로 검색해보세요

nosqeil24 8년 전 1

제 소스입니다. 혹시 이해가 안되신다면 참고해보세요!

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int n,k,arr[111];
int cache[2][11111];
int main()
{
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++)
        scanf("%d",&arr[i]);
    for(int i=0;i<111;i++)
        for(int j=0;j<11111;j++)
            cache[i%2][j]  = 0;
     
    for(int i=0;i<111;i++)
        cache[i%2][0] = 1;
     
    for(int j=1;j<=k;j++)
        cache[n%2][j] = 0;
     
    for(int i=n-1;i>=0;i--)
    {
        for(int j=1;j<=k;j++)
        {
            cache[i%2][j] = 0;
            for(int q=0;;q++)
            {
                if(j-arr[i]*q < 0) break;
                cache[i%2][j] += cache[(i+1)%2][j-arr[i]*q];
            }
        }
    }
    printf("%d\n",cache[0][k]);
}

indioindio 8년 전 1

5, 3, 1원이 있는데 10원짜리를 만들고자 한다면

10원을 만드는 경우의 수는 5원을 만드는 경우의 수 + 7원을 만드는 경우의 수 + 9원을 만드는 경우의 수라는 걸 생각해보시면 도움이 될 것 같네요

sgc109 8년 전 0

@indioindio

5, 3, 1 원으로

10원을 만드는 경우의 수 = 7

9원을 만드는 경우의 수 = 6

7원을 만드는 경우의 수 = 4

5원을 만드는 경우의 수 = 3

7 = 6 + 4 + 3 ???

음 뭔가 잘못된것같네요

sgc109 8년 전 0

@nosqeil24

아 전에 본능적으로 모듈라연산으로 메모리 초과를 해결한적이 있었어서 이걸 쓸려고했었는데

이 문제와 같은 경우에는 dp 의 모든 원소가 계속 사용된다고 생각해서 사용하지못했는데

'dp[k][i] 를 채우기 위해서는 dp[k'][i-1] (0<=k'<=k)의 값이 필요합니다.' 이 부분이 이해가 갈듯말듯합니다..

저와 D(i,j) 를 다르게 잡으셔서 헷갈리는것 같기도하고.. 저는 dp 에서 열의 인덱스가 작을 수록 더 크거든요.. 아니면 그냥 제가 이해를 잘못하는건가요 ㅠㅠ 으 머리속이 꼬인기분이에요

indioindio 8년 전 1

아아 제가 다른 문제랑 헷갈려서 표현을 이상하게 했네요 ㅋㅋ

각 동전 n원에 대해서, k원을 만드는 법은

k - n의 경우의 수와 같은 거였네요(이 표현도 쓰고보니 조금 이상한거같지만)

1 3 5로 10원을 만든다면

1원으로는 1 ~ 10까지 올라가면서 한 가지 경우로 만들수 있고(0원을 내는 경우의 수가 1이라면요)

3원으로 3원을 만든다면, 3원을 1동전을 이용한 한 가지 방법으로 이미 만들수 있으므로 2… 이렇게 하시면 될 듯 합니다

현재까지 등장한 동전으로 만들 수 있는 금액의 경우의 수를 가지고 있으므로 1차원 배열로 할 수 있을 것 같네요

h0ngjun7 8년 전 2

1차원으로 정의하여 누적하며 계산할 수 있습니다.

#include <stdio.h>
int n, k, x;
int d[10005];
int main() {
    scanf("%d%d", &n, &k);
    d[0] = 1;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        for (int j = 0; j <= k - x; j++) {
            d[j + x] += d[j];
        }
    }
    printf("%d", d[k]);
}

sgc109 8년 전 0

@hongjun7

아... 이런방법이...

감사합니다!

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

문제

문제

출처

ICPC

'DP와 함께하는 알파벳공부' D 번-동전1 문제 질문좀하겠습니다.

sgc109 8년 전 0

nosqeil24 8년 전 1

nosqeil24 8년 전 1

indioindio 8년 전 1

sgc109 8년 전 0

sgc109 8년 전 0

@nosqeil24

indioindio 8년 전 1

h0ngjun7 8년 전 2

sgc109 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말