* Computer Science/Algorithm

baekjun 2293. 동전1

soicem 2018. 8. 8. 18:44

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


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

 

 

 

 

 1+1

 2

 

 

 1+1+1

 1+2

 3

 

 1+1+1+1

 1+1+2

 1+3

 4


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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;
}
cs