뚝배기 터진 문제_boj
boj2293 동전 1
헐랭미
2020. 6. 24. 15:41
https://www.acmicpc.net/problem/2293
메모리 초과를 어떻게 개선할까 하다가 결국엔 못푼 문제이다.
기존 코드이다. 4byte*100만 = 4MB 이니 당연히 터진다.
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#include <iostream>
#include <vector>
#include <algorithm>
#define pii pair<int, int>
using namespace std;
int d[10001][100] = { 0 };
int arr[100];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> arr[i];
sort(arr, arr + n);
for (int i = 0; i < n; i++)
{
if (arr[i] <= 10000)
d[arr[i]][i] = 1;
}
for (int i = 1; i <= k; i++)
{
for (int j = 0; j < n; j++)
{
if (i - arr[j] >= 0)
{
for (int k = 0; k <= j; k++)
d[i][j] += d[i - arr[j]][k];
}
}
}
/*
for (int i = 1; i <= k; i++)
{
for (int j = 0; j < n; j++)
{
cout << d[i][j] << ' ';
}
cout << '\n';
}
*/
int ans = 0;
for (int i = 0; i < n; i++)
ans += d[k][i];
cout << ans;
}
|
cs |
여기서 내가 시간이 오래걸린 이유는 i를 k로, j를 n으로 생각해서 오래 걸렸다.
i를 n으로 j를 k로 해서
d[10001] 로 잡고 하니깐 풀렸다.
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
33
34
|
#include <iostream>
#include <vector>
#include <algorithm>
#define pii pair<int, int>
using namespace std;
int d[10001] = { 0 };
int arr[100];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> arr[i];
sort(arr, arr + n);
d[0] = 1;
for (int i = 0; i < n; i++)
{
for (int j = 1; j <= k; j++)
{
if (j - arr[i] >= 0 )
d[j] += d[j - arr[i]];
//cout << d[j] << ' ';
}
//cout << '\n';
}
cout << d[k];
}
|
cs |
근데 다시 생각해보면 이 문제의 더 핵심적인 키워드는 21줄의 d[0] = 1를 잡아주는게 아닐까 싶다...