baekjun 2293. 동전1

 첫 번째는 재귀로 짰다가 메모리 공간을 줄일 방법을 못찾아서 이터레이션으로 바꾼 문제.

 int 1000만개에 40mb이므로 10000 * 100은 100만이니 4mb를 넘는다는 사실을 알 수 있다.  따라서 배열을 줄여야하는데 그에 대한 방법은 아래와 같다.

 

1
1+1	2
1+1+1	1+2	3
1+1+1+1	1+1+2	1+3	4

#include <iostream>
 
using namespace std;
 
int N, K;
int coins[101];
int D[10001];
 
 
/*
D(i, k) = {
    D(i -1, k) if C(i) < K
    D(i -1, k) + D(i, k - C[i]) if C(i) >= K
}
*/
 
int main() {
    cin >> N >> K;
    for (int i = 1; i <= N; i++)
        cin >> coins[i];
    D[0] = 1;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= K; j++) {
            if (j >= coins[i])
                D[j] += D[j - coins[i]];
        }
    }
    cout << D[K] << endl;
    system("pause");
    return 0;
}