백준 11047 - 동전 0(C++)

문제 링크입니다. https://www.acmicpc.net/problem/11047

11047번: 동전 0

그리디의 대표적인 문제입니다.

필요한 동전의 최솟값을 구하는 방법은 값이 높은 동전을 최대한 이용하는 방법입니다.

따라서 큰 가치의 동전부터 사용하면서 내려가면 되는 문제입니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>

using namespace std;

int N, K, sum;
int coin[1000001];

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> N >> K;
    for (int i = 1; i <= N; i++) cin >> coin[i];
    for (int i = N; i >= 1; i--) {
        if (coin[i] <= K) {
            sum += K / coin[i];
            K %= coin[i];
        }
    }
    cout << sum;
    return 0;
}

 

질문 및 조언 댓글 남겨주세요