[ 백준 2294 ] 동전2 (C++)

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

2294번: 동전 2

 

문제를 읽고 bfs로 풀면 되겠다고 생각해 bfs로 풀었다. 아이디어는 간단하다. 모든 동전마다 몇 개의 동전이 필요한지 저장해주는 map이라는 1차원 배열을 생성한다.

 

만약에 사용 가능한 동전이 1,3원 이라고 가정하면,

map[5] = 5원을 만드는 최소 동전(1,3원) 개수
map[8] = 8원을 만드는 최소 동전(1,3원) 개수
map[n] = n원을 만드는 최소 동전(1,3원) 개수

 

map의 의미를 알았다면 그림으로 살펴보자. 문제의 예제로 예를 들어보겠다.

 

 

가용 동전을 하나만 가지고 만들 수 있는 액수는 각각 1, 5, 12원이기 때문에 map[n] = 1 가 성립한다.

1원에서 가용 동전을 하나씩 써서 만들 수 있는 액수는 2, 6, 13원이고, 총 동전 두 개를 써서 map[n] = 2 가 성립한다.

5원에서 가용 동전을 하나씩 써서 만들 수 있는 액수는 6, 10, 17원이고, 총 동전 두 개를 써서 map[n] = 2가 성립한다.

12원에서 가용 동전을 하나씩 써서 만들 수 있는 액수는 13, 17, 25원이고, 총 동전 두 개를 써서 map[n] = 2가 성립한다.

 

이런식으로 계속 반복하면 된다. 

 

알고리즘은 아래와 같다. 

map[available coin] = 1 초기화
1. 큐에 coins에 있는거 다 넣어준다
2. 큐 빌때까지 아래를 반복한다.
----1) 큐 pop (front 값을 idx라고 하자)
----2) map[idx+coins[i]] 검사
----3) 2)의 값이 0이면 (idx+coins[i]) push해주고, map[idx + coins[i]] = map[idx] + 1 로 갱신

 

 

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

// 1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000
int map[10001];
vector<int> coins;
int n, k, idx, tmp;
 
void bfs(){   
    queue<int> q;
    for(int i = 0; i < coins.size(); i++){
        q.push(coins[i]);
    }
    
    while(!q.empty()){
        idx = q.front();
        q.pop();
        for(int i = 0; i < coins.size(); i++){
            if(idx + coins[i] <= 10000){
                if(map[idx + coins[i]] == 0){
                    map[idx + coins[i]] = map[idx] + 1;
                    q.push(idx + coins[i]);
                }
            }
        }
    }
}


int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> tmp;
        if(tmp <= 10000){
            coins.push_back(tmp);
            map[tmp] = 1;
        }
    }
    
    bfs();
    
    if(map[k] == 0)
        cout << -1 << endl;
    else
        cout << map[k] << endl;
    
    return 0;
}