[BaekJoon 11047번] 동전 0(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

11047번: 동전 0

 

 

[문제 설명]

 

 

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

 

[입력]

 

 

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

 

 

[출력]

 

 

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

 

[입출력 예]

 

 

입력	출력
10 4200 1 5 10 50 100 500 1000 5000 10000 50000	6
10 4790 1 5 10 50 100 500 1000 5000 10000 50000	12

 

 

[문제 풀이]

 

 

그리디 문제이다.

이 문제에서 중요한 조건은 'i ≥ 2인 경우에 Ai는 Ai-1의 배수' 이다.
Ai 한개는 Ai-1 여러개라는 의미가 된다. 

즉, Ai를 사용할 수 있다면, Ai-1 쓰는 것보다 무조건 이득!이라는 뜻이다.

 

그래서 동전의 가치를 입력 받고 내림 차순 정렬해주었다.

입출력 예시로 내림 차순 정렬 하게 되면 아래와 같이 내림 차순 정렬된다.

50000, 10000, 5000, 1000, 500, 100, 50, 10, 1

 

화폐 단위가 큰 것부터 나누어 주고 나눈 몫이 동전의 개수를 의미한다.

그리고 남은 가치는 나머지 연산을 함으로서 얻을 수 있다.

 

 

같은 문제로 거스름돈 문제가 있다. 같이 풀어보도록 하자.

5585번: 거스름돈

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <bits/stdc++.h>
using namespace std;

vector<int> coin;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K; cin >> N >> K; // 동전 종류, 가치
    for(int i = 0; i < N; ++i) {
        int n; cin >> n;
        // 동전의 가치
        coin.emplace_back(n);
    }
    sort(coin.begin(), coin.end(), greater<int>()); // 내림 차순 정렬
    int result = 0;
    for(int i = 0; i < N; ++i) {
        result += (K / coin[i]);
        K %= coin[i];
    }
    cout << result;
    return 0;
}