문제
N종류의 동전을 사용해 K의 값을 만들 때 필요한 동전을 최소화하기
동전의 가치가 오름차순으로 주어진다
생각할 것
가지고 있는 동전을 최소화해야 하므로 큰 단위의 동전을 나눌 수 있는 만큼 최대한 나눈다.
→ 그리디 알고리즘을 이용한다.
코드
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, K;
cin >> N >> K;
vector<int> vec(N); // 동전 가치
for (int i = 0; i < N; i++) {
cin >> vec[i];
}
int coin = 0;
for (int i = N - 1; i >= 0; i--) {
if (K >= vec[i]) {
int tmp = K / vec[i];
coin += tmp;
K -= (tmp * vec[i]);
}
}
cout << coin;
return 0;
}
반응형
'Problem solving > BOJ' 카테고리의 다른 글
[BOJ] 2493. 탑 (C++) (0) | 2023.08.11 |
---|---|
[BOJ] 1182. 부분수열의 합 (C++) (0) | 2023.08.08 |
[BOJ] 1149. RGB거리 (C++) (0) | 2023.08.08 |
[BOJ] 5427. 불 (C++) (0) | 2023.08.08 |