#11047 동전 0

문제 정리

다 약수관계인 동전, 동전 개수 최솟값 보자마자 -> 그리디!
N, K 입력받고 동전 종류 N개로 K원 만드는 데 드는 동전 개수의 최솟값 출력

생각해보기

근데 이게 동전 종류도 입력받는거라 약수관계가 안 될 수 있겠다고 생각이 들긴 드는데..
A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수 라는 조건이 있네! 그럼 무족건 그리디.

그리디 틀어~~~!!!

코드 쓰기

내림차순 정렬 외에는 저번 동전 문제(#5585 거스름돈)이랑 로직은 똑같다.

내 풀이

// BOJ-11047 동전 0
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n = 0, k = 0;
    int answer = 0;
    vector<int> v;

    cin >> n >> k;

    for(int i = 0; i < n; i++){
        int coin = 0;
        cin >> coin;
        v.push_back(coin);
    }

    // 벡터 내림차순 정렬
    sort(v.begin(), v.end(), greater<int>());

    for(int i=0; i<v.size(); i++){
        if (k / v[i] != 0) {
            answer += k / v[i];
            k %= v[i];
        }
    }

    cout << answer;
}

풀고 나서 알게된 것

벡터 내림차순 정렬

// 벡터 내림차순 정렬
sort(v.begin(), v.end(), greater<int>());

greater<int>() 이거다..

sort(v.end(), v.begin());

써서 런타임 오류 맞았다… ^^ ㅋㅋ