boj2293 동전 1

https://www.acmicpc.net/problem/2293

2293번: 동전 1

 

메모리 초과를 어떻게 개선할까 하다가 결국엔 못푼 문제이다.

기존 코드이다. 4byte*100만 = 4MB 이니 당연히 터진다.

#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;
}

 

여기서 내가 시간이 오래걸린 이유는 i를 k로, j를 n으로 생각해서 오래 걸렸다. 

 

i를 n으로 j를 k로 해서 

d[10001] 로 잡고 하니깐 풀렸다.

 

 

#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];
}

근데 다시 생각해보면 이 문제의 더 핵심적인 키워드는 21줄의 d[0] = 1를 잡아주는게 아닐까 싶다...