* Computer Science/Algorithm
baekjun 2293. 동전1
soicem
2018. 8. 8. 18:44
첫 번째는 재귀로 짰다가 메모리 공간을 줄일 방법을 못찾아서 이터레이션으로 바꾼 문제.
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 |
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 |