[백준][C++] 2293: 동전 1

문제 링크: https://www.acmicpc.net/problem/2293

 

dp 문제입니다. 메모리 제한이 4MB로 빡빡합니다.

int dp[10001][100] 이렇게 배열을 만들면 100만*4바이트 = 4MB가 됩니다. 기본적으로 입출력에 사용되는 메모리 양을 합치면 무조건 메모리 초과가 나오죠

 

그래서 좀 다르게 풀어야 합니다. 저는 1차원 dp 배열을 누적시키는 방법으로 풀었습니다.

 

dp[0][0] = 1;
for (int i = 1; i <= 10000; ++i) {
    for (int j = 0; j < coins.size(); ++j) {
        if (i - coins[j] < 0) break;

        for (int k = 0; k <= j; ++k) {
            dp[i][j] += dp[i - coins[j]][k];
        }
    }
}

cout << accumulate(dp[k], dp[k] + n, 0) << '\n';

메모리 초과가 나는 코드입니다.

 

// 2293

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;


int dp[10001];

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int n, k;
	cin >> n >> k;
	vector<int> coins(n);
	for (auto& c : coins)
		cin >> c;

	dp[0] = 1;
	for (auto& c : coins) {
		for (int i = c; i <= k; ++i) {
			dp[i] += dp[i - c];
		}
	}

	cout << dp[k] << '\n';

	return 0;
}

여기서 dp[i]: i원을 만드는 방법의 개수입니다

 

동전이 1, 2, 5원짜리가 있을 때 누적되는 dp 배열을 그려보면 아래와 같습니다

i | 1  2  3  4  5  6  7  8  9 10
--------------------------------
1 | 1  1  1  1  1  1  1  1  1  1
2 | 0  1  1  2  2  3  3  4  4  5
5 | 0  0  0  0  1  1  2  2  3  4
--------------------------------
s | 1  2  2  3  4  5  6  7  8 10

순서 상관 없이 각 동전 별 dp배열을 누적시키면 됩니다.

 

처음 풀어보는 방식이라 좀 어려웠습니다;; 그리고 dp 문제에 메모리 제한이라니 으으 싫네요 ㅠ