[백준/C++/Greedy] 11047 동전 0

0. 문제

동전 0 / 실4 / 11047 / greedy

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

인풋된 여러 종류의 동전으로 목표 금액을 만들 때

동전의 개수를 최소화하는 문제이다

 

동전 종류의 수도 입력하고

동전의 가치도 오름차순으로 인풋된다

 

1. 테스트 케이스 분석

.

백준에 있는 예시

첫 줄은 동전의 종류 수와 목표 금액

이후에는 동전의 가치가 종류 수만큼 입력된다

 

해당 예시에서는 10가지 종류의 동전들을 이용해서

목표 금액 4200원을 만드는 조합들 중

최소 동전 개수를 구하는 것이다

 

눈으로 보아도 4200 = 1000 x 4 + 100 x 2 임을 알 수 있으나

차근차근 생각해보자면

 

입력된 동전의 가치 중 목표 금액을 초과하는 동전들로는 구할 수 없으니 제외해야하고 

인풋 값이 오름차순 정렬로 되어 있기 때문에 제외하기 쉽다

 

목표 금액보다 작은 동전들 중

가치가 큰 동전들부터 내림차순으로 사용해야 

동전의 개수를 최소화할 수 있다

 

4200 = 1000 x 4 + 100 x 2 에서도

4200보다 작은 동전들 중 가장 큰 동전은 1000이므로 

1000으로 최대한 가깝게 만들면 4000

 

4200-4000=200이 남으므로

남은 200원보다 작으면서 가장 큰 동전은 100이기 때문에

100으로 200을 만든다

 

 

2. 코드 구상

 

동전 종류의 수를 n으로 

목표 금액을 k로 두고

 

n개의 동전 종류는 오름차순으로 이미 정렬되었으니

반복문을 돌며 코인 벡터에 동전 종류를 저장하고

목표 금액보다 큰 가치의 동전은 제외하고

작은 가치의 동전을 활용해서 계산하기로 한다

 

이때 반복문은 n개의 동전 종류에 대해 루프를 도는데

큰 가치부터 역순으로 탐색할 것이기 때문에

n-1부터 0까지 n번 돌기로 했다

 

작은 가치의 동전을 활용해서 계산할 때는

목표 금액보다 작은 가치 중 가장 큰 가치로 

목표 금액을 나누고 

그 몫은 동전 개수로 카운트 하고

나머지는 다른 동전으로 만들어야 하는 남은 금액이므로

그 나머지를 새로운 목표 금액으로 갱신한다

 

3. 코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, k;  // n 동전 종류 수 / k 목표 금액
    cin >> n >> k;

    vector<int> coin(n);  // n가지 동전
    for (int i = 0; i < n; i++) {
        cin >> coin[i];  // 동전 가치
    }

    int cnt = 0;  // 카운트

    // 동전의 큰 단위부터 계산하려고 거꾸로 !!
    for (int i = n - 1; i >= 0; i--) {
        if (coin[i] <= k) {
            cnt += k / coin[i];  // 현재 동전으로 카운트
            k %= coin[i];        // 목표 금액 갱신

            // 목표 금액 0 되면 끝
            if (k == 0) break;
        }
    }

    cout << cnt << endl;  // 출력

    return 0;
}