195번째 문제 - 2293 동전1

평소대로 메모리 신경안쓰고 재귀로 해결하니 (보통 100메쯤 주니까 ... 이 문제는 확인해보니 4메가)  메모리 초과로 오답을 받았다. 이차원배열이던 dp 배열을 1차원으로 바꾸고 2차원 반복문으로 해결했다. 점화식이 간단하니 점화식 설명은 생략

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main()

{

int cache[10001] = { 1,0 };

vector<int > cur;

int c, m, t;

cin >> c >> m;

while (c--) {

cin >> t;

cur.push_back(t);

}

sort(cur.begin(), cur.end());

for (int i = 0; i < cur.size(); i++) {

for (int j = cur[i]; j <= m; j++) {

cache[j] += cache[j - cur[i]];

}

}

cout << cache[m];

}