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

문제 출처: https://www.acmicpc.net/problem/2293

2293번: 동전 1

n가지 종류의 동전을 0번 이상 사용하면서 그 가치의 합이 k가 되도록하는 문제는 dp에서 자주 보았기 때문에

Top-Down으로 [사용한 동전 idx][현재 가치]를 파라미터로 가지는 함수를 작성하여 각 동전의 종류마다

0~10001(동전의 수* 동전의 가치 > k 인경우 break)개를 사용하는 방법으로 작성하였고 이후 메모리 초과가 떠서 다른 방법을 생각해봄

 

이전에 풀어봤던 평범한 배낭 2 와 같이 0~N개의 아이템을 사용할 수 있을 때 2의 제곱 개씩 묶어서 서로 다른 아이템으로 표현하여 시간 복잡도를 줄이는 방법이 떠올라 해당 방법을 적용 후 제출했지만 또 메모리 초과가 떴다.

해당 방법의 문제는 메모리를 더 많이 사용하여 시간복잡도를 줄이는 방법이기 때문에 당연히 메모리 초과가 뜬다.

 

해당 문제는 강제로 Bottom-up 방식으로 풀게하려고 메모리 제한을 걸어둔 것이다.

Top-Down 방식은 재귀적 함수 호출 과정에서 메모리 초과가 뜰 수 밖에 없다.

Top-Down 방식으로만 풀다가 Bottom-Up으로 풀려하니 생각보다 까다로워졌다.

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <string>
using namespace std;


int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);


    int n, k;

    cin >> n >> k;
    int arr[101];
    for (int i = 0; i < n; i++)cin >> arr[i];


    int dp[10001] = {};
    dp[0] = 1;

    //i번째 동전을 쓸 차례
    for (int i = 0; i < n; i++) {

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

    cout << dp[k];
    


}