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

https://boj.kr/2293 

2293번: 동전 1

 

배낭문제를 활용하는 알고리즘이라는데, 전 다이나믹 프로그래밍이 더 자연스러운 것 같았습니다.

중간에 메모리 초과가 나와서 더 당황했네요.

 

해당 문제는 자연수의 분할 문제로 생각해서 볼 수 있습니다. 다만 분할될 수 있는 자연수의 종류가 제한된 경우이죠.

 

동전이라서 처음엔 아무 생각 없이 그리디라고 생각하고 보았으나,

제일 큰 동전의 개수를 기준으로 메모이제이션 하면 되니 DP 문제에 가까웠습니다.

 

문제의 예시를 기준으로 생각해보겠습니다.

 

만약 내가 1 2 5라는 동전들이 무수히 있고, 이를 통해 10이라는 숫자를 만들어야한다고 할 때,

일단 제일 큰 동전부터 보는겁니다. 5 짜리 동전 몇개로 만들 수 있는지 생각해봅시다.

5짜리 동전을 한개만 써서 만들 수도 있고, 두개를 써서 만들 수도 있고, 아예 안쓸 수도 있습니다.

 

이때, 5짜리 동전의 개수를 다 구했다면?

5짜리 동전을 더이상 사용하지 않고 만들 수 있는 경우는 1, 2로 수를 만드는 경우에서 가져오면 됩니다. 이 과정에서 메모이제이션이 사용됩니다. 1, 2로 10을 만드는 경우를 생각해볼 수도 있고, 5를 만들 경우를 생각할수도 있고, 0을 만드는 경우를 생각할수도 있을 겁니다.

 

네, 모든 경우에 대해서 다 생각해봐야하므로 우리는 만들어야하는 수가 K일때, 0부터 K에 대해서 모두 생각해봐야합니다.

이런 식으로 가장 작은 수의 동전만으로 만드는 경우의 수를 소급해나가면 됩니다.

 

다만 제일 큰 동전부터 선택한 후에 제외하기 시작한다면, 그의 작은 수를 가진 동전들로 이루어진 경우의 수들을 가져와서 참고해야 하기 때문에 따로 메모이제이션을 해야합니다. (또는 다른 방법이 있겠지만 더 복잡할 겁니다.) 따라서 우리는 메모이제이션하는 배열의 크기를 동전의 수는 최대 100개, K의 최댓값은 100000이므로 100000*100 크기의 배열을 생각할 수 있습니다.

 

다만 이렇게 한다면, 경우의 수는 2^31보다 작으므로 이를 나타낼 수 제일 작은 자료형인 int(4바이트)*천만 이므로 대략적으로 봤을 때 4천만 바이트 = 4메가바이트에 해당합니다. 따라서 메모리 초과가 일어나는 것이고,, 우리는 좀 더 작은 공간을 활용해야합니다.

 

따라서 바텀업(제일 작은 수를 나타내는 동전부터 그 위의 동전을 포함해서 경우의 수를 만들어 나가는 과정)을 통해 dp 메모이제이션을 시작하면,

 

3번째 로 제일 작은 동전을 포함하여 0부터 K까지의 수를 담을 때(a_3), 가장 작은 동전으로만 이루어진 경우(a_1)의 정보를 참고하지 않아도 됩니다.

 

(왜냐하면 3번째로 제일 작은 동전을 포함하는 경우를 계산하면 바로 밑의 a_(n-1)의 경우만 생각하면 되니까요.)

 

따라서 이렇게 된다면 우리는 그 전 단계의 정보만 있으면 됩니다. 그렇게되면 100000*100에서 100000*2로 필요한 공간이 줄어들게 됩니다.

 

해당 방식을 이용하여 코드를 만들면 아래와 같이 만들어집니다.

 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int dp[100001];
int temp[100001]; // 100000*2

int coins[100];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, K; cin>>N>>K;

    for(int i=0; i<N; ++i) cin>>coins[i];
    sort(coins, coins+N);
    dp[0] = 1;
    for(int n=0; n<N; ++n) {
        for(int k=0; k<=K; ++k) {

            if(k == 0) {
                temp[k] = 1;
                continue;
            }

            int temp_k = k;

            while(temp_k >= coins[n]) {
                temp_k -= coins[n];
                temp[k] += dp[temp_k];
            }
        }
        memcpy(dp, temp, sizeof(dp));
    }
    cout<<dp[K];
}

 

질문 환영합니다.