Baekjoon 2293번 동전 1

문제

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

걸린 시간

00 : 42 : 38 실패

시간 초과 풀이

C++

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

int n, k;
int coin[100];
map<pair<int, int>, int> cache;

int solve(int idx, int val){
    // 기저 사례
    if(val == k)
        return 1;
    // 메모이제이션
    int& ret = cache[make_pair(idx, val)];
    if(ret != 0)
        return ret;
    // 재귀 호출
    for(int i = idx; i < n; i++)
        if(val+coin[i] <= k)
            ret += solve(i, val+coin[i]);
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    for(int i = 0; i < n; i++)
        cin >> coin[i];
    cout << solve(0, 0);
    return 0;
}

동전의 가치가 오름차순으로 정렬 된 상태에서 가치가 같거나 큰 동전들만 재귀로 호출을 할 경우 조합을 구할 수 있다. 하지만 4mb 메모리 제한으로 동전 인덱스와 가치의 합을 이용한 메모이제이션의 캐쉬 배열의 사용이 불가능하다. 배열 대신 map 을 사용하면 메모리 초과를 해결할 순 있어도 각 단계별로 O(logN) 의 탐색 시간이 추가로 들어 시간초과가 발생한다.

옳은 풀이

C++

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    int coin[100], cache[10001];
    for(int i = 0; i < n; i++)
        cin >> coin[i];
    memset(cache, 0, sizeof(cache));
    cache[0] = 1;
    for(int i = 0; i < n; i++)
        for(int j = coin[i]; j <= k; j++)
            cache[j] += cache[j-coin[i]];
    cout << cache[k];
    return 0;
}

조금 고민을 하다 재귀로는 도저히 해결이 되지 않을 것 같아 바로 풀이를 보았는데 문제를 처음 접하는 많은 사람들이 나처럼 재귀로 접근하다 실패한 것 같았다. 찾아본 풀이 방법 외에, 슬라이딩 윈도우 기법을 적용한 풀이도 있으니 추가로 공부해보아야겠다.

참고

• BOJ 2293번 :: 동전 1 :: okayoki
• [백준알고리즘] 2293번: 동전 1 -C