[BOJ-2293]동전1

첫번째 작성했던 것은 """메모리초과""" 를 받았다. 

일단 

 

위 방정식을 생각했는데

f(n,k) : k 값을 n개의 동전으로 만들기 위한 가짓수.

f(n, k-coin[n]) ; n개의 동전중 coin[n]을 한번 사용해서 k-coin[n] 일 때 n개 동전을 사용하는 것을 구함.

f(n-1, k) ; n-1개 동전으로 k를 구함.

입력으로 주어진 coin n개 중 coin[n]을 사용해서 값을 구하는 것을 재귀함수로 호출하여 풀이하려고 했다.

근데 메모리초과? 길래 4MB 가 제한 기준인 걸 보고서... 다시 생각을 해야했었음..

#include<cstdio>
#include<vector>
using namespace std;
typedef vector<int> VI;
VI want[101];
VI coin;
 
int dy(int n,int k) {
    if (k < 0 || n <= 0) return 0;
    if (k == 0) return 1;
    //int& ret = want[n][k];    
    if (want[n][k] != -1) return want[n][k];
    want[n][k] = dy(n - 1, k) + dy(n, k - coin[n]);
    return want[n][k];
}
 
int main() {
    int n, k; scanf("%d%d", &n, &k);
    coin = VI(n + 1, 0);
    for (int i = 0; i < 101; i++) {
        want[i] = VI(10001, -1);
    }    
    for (int i = 1; i <= n; i++) {
        scanf("%d", &coin[i]);        
    }    
    printf("%d", dy(n,k));    
    return 0;
}
 

다른 생각으로 

동전이 예제와 같이 

3 10

1

2

5

want = 10

coin[] = {1,2,5}

 

첫번째 coin[0] 을 가지고 10을 만들 수 있는 경우를 먼저 갱신하고

coin[1]을 가지고 10을 만들 수 있는 경우를 갱신

....

coin[n-1]  개 를 가지고 만들 수 있는 경우를 갱신하며 memo[want]에 적힌 값을 출력하면 되는 문제였다.

그렇게 되면 재귀적으로 하지 않고 배열또한 100 * 10000 = 1,000,000 크기를 사용하지 않아도 10000개 까지만 사용해도 되었었다.

#include<cstdio>
#include<vector>
using namespace std;
 
typedef vector<int> VI;
 
int main() {
    int n, k; scanf("%d%d", &n, &k);
    VI memo = VI(k+1, 0);
    VI coin = VI(n, 0);
    memo[0] = 1;
    for (int c = 0; c < n; c++) {
        scanf("%d", &coin[c]);
    }
    for (int c = 0; c < n; c++) {
        for (int w = 1; w <= k; w++) {
            if (w - coin[c] >= 0) {
                memo[w] += memo[w - coin[c]];
            }
        }
    }
    printf("%d", memo[k]);
    return 0;
}