[ BOJ / C++ ] 2294번 : 동전 2

[ BOJ ] 2294번 : 동전 2

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

---

[  문제  ]

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

[  입력  ]

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

[  출력  ]

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

---

[  문제 접근 및 풀이  ]

먼저 Vector에 가치가 각각 다른 동전을 넣어준 후에

동전의 가치인 인덱스에 개수 1개를 넣어주었고

for문을 돌면서 가치가 $i$원일 때 현재 가치의 동전의 최소 개수와

동전 x원의 가치를 뺀 동전의 개수 상태 + 1을 확인 해서 최솟값을

$i$원에 넣는 작업을 돌렸다.

이후 $k$원에 맞지 않는 값이 들어가있다면 불가능한 경우이기에 -1

알맞는 값이 있다면 최소 개수를 출력하였다.

 

[  소스 코드  ]

#include<bits/stdc++.h>
using namespace std;
int N,K;
int D[10001];
vector<int> V;
bool vis[10001];
void Q_2294();
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	Q_2294();
}
void Q_2294(){
    cin >> N >> K;
    for(int i=0;i<=K;i++) D[i]=1234567890; //동전 개수
    for(int i=0;i<N;i++){
        int a;
        cin >> a;
        if(a>K || vis[a]) continue;
        vis[a]=true;
        D[a]=1;
        V.push_back(a);
    }
    for(int i=1;i<=K;i++){
        for(auto x:V){
            if(i>x) D[i]=min(D[i],D[i-x]+1); //가치가 i일 때 현재 동전 개수 상태와 동전x원을 들고 있을 때 개수 
        }
        
    }
    if(D[K]==1234567890) cout << -1;
    else cout <<D[K];
}

---