[백준 #11047] 동전 0 (C++)

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

11047번: 동전 0

동전의 종류 N개와 동전으로 만들 합 K를 입력하고

for 문을 사용해 N가지의 동전 값을 입력받아

K보다 작은 것들만 벡터에 넣어주었다.

(K보다 큰 동전 값은 필요가 없기 때문이다.)

 

그리고 큰 동전 값부터 나누기 위해 reverse를 사용하여 벡터를 내림차순으로 정렬시켰다.

(동전 값을 오름차순으로 입력했기 때문)

 

그다음 for 문을 사용해 N이 1일 때는 (동전 종류가 1가지 일 때)

K를 vec[0]로 나눈 몫을 cnt에 넣은 후 break로 for 문을 나가고,

아닐 시에는 K가 동전 값으로 나눠진다면 그 몫을 cnt에 더해주고

K는 나머지 값이 되게 하였다.

 

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K, num;
    int cnt = 0;
    vector <int> vec;

    cin >> N >> K;

    for (int i = 0; i < N; i++) {
        cin >> num;
        if (num <= K)
        vec.push_back(num);
    }

    reverse(vec.begin(), vec.end());

    for (int i = 0; i < vec.size(); i++) {
        if (N == 1) {
            cnt = K / vec[0];
            break;
        } else {
            if (K / vec[i] > 0) {
                cnt += K / vec[i];
                K %= vec[i];
            } else continue;
        }
    }
    cout << cnt;
    return 0;
}