백준 동전 2 [c++]

2294 동전 2 골드 5

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

풀이

동전1과 다르게 BFS로 풀어볼 수 있겠다고 생각되어 BFS로 풀어보려 했다.

처음에는 동전 종류를 큐에 넣고 하나씩 꺼내며 모든 종류의 동전을 더해가며 풀려했는데, 이러면 큐가 너무 많이 생겨 메모리 초과가 났다. (메모리 128MB 제한)

그래서 메모이제이션하면서 map배열에 index금액을 만드는데 든 동전 수를 저장하기로 함.

BFS를 사용하기 때문에(큐: 선입선출), 5원 3개를 쓴 경우가 (12원 1개, 1원 3개)를 쓴 경우보다 먼저 나오게 되어 최소값을 유지해줄 필요가 없다.

memset사용.

처음 map을 (map[10001] = { -1, })로 초기화했는데, -1로 초기화 되지 않고 처음만 -1, 나머지는 0으로 초기화되었다.

직접 초기화해주거나 memset을 사용해야겠다.

코드

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

int n, k;
vector<int> coin;
int map[10001];
int minUsed = 100000;

void bfs()
{
    queue<int> q;
    for(int i = 0; i < n; i++)
    {
        if(coin[i] <= k){
            map[coin[i]] = 1;
            q.push(coin[i]);
        }
    }

    while(!q.empty() && map[k] == -1) 
    {
        int sum = q.front();
        // cout << "[" << sum << "]\n";
        q.pop();
        
        // if(sum == k){
        //     if(used < minUsed){
        //         minUsed = used;
        //     }
        // }

        for(int i = 0; i < n; i++)
        {
            if(sum + coin[i] <= 10000 && map[sum + coin[i]] == -1){
                map[sum + coin[i]] = map[sum] + 1;
                q.push(sum + coin[i]);
            }
        }
    }
}

int main()
{
    cin >> n >> k;

    for(int i = 0; i < n; i++)
    {
        int tmp;
        cin >> tmp;
        coin.push_back(tmp);
    }
    memset(map, -1, sizeof(map));
    sort(coin.begin(), coin.end());
    bfs();


    cout << map[k] << endl;
    
    return 0;
}

• ps
• dp
• bfs