[BOJ-11047][C++] 동전 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

예제 입력 1

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

 

예제 출력 1

6

 

예제 입력 2 

10 4790
1
5
10
50
100
500
1000
5000
10000
50000

 

예제 출력 2

12

 

알고리즘 분류

• 그리디 알고리즘

 

문제 출처

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

11047번: 동전 0

 

---

 

문제 해결 방법

• 그리디 알고리즘을 이용하여 문제를 해결하였다.
• @K@ 개의 수들을 벡터(@values@)에 넣은 후, 내림차순 정렬을 해다.
• for 문을 이용하여 가치가 큰 수부터 작은 수까지 하나 하나씩 나눠주면서 나온 몫들의 총합(@cnt@)을 출력해주도록 하였다.
  • 몫들의 총합을 업데이트해줌(@cnt += (k / i)@)과 동시에 @k@ 값 또한 업데이트 해줘야 한다. (@k -= ((k / i) * i)@)

int Solution(int k) {
    sort(values.begin(), values.end(), greater<int>());    // 내림차순 정렬

    for (auto i : values) {
        if (i <= k) {
            // cout << "[i] : " << i << " [k / i] : " << k / i << " ";
            cnt += (k / i);
            // cout << "[cnt] : " << cnt << " ";
            k -= ((k / i) * i);
            // cout << "[k] : " << k << '\n';
        }
    }
    return cnt;
}

※ 주석 처리된 부분은 디버깅 용도이다.

 

예제를 이용하여 알고리즘 이해하기

• @예제 입력 2@의 값들을 이용하여 알고리즘을 이해해보자.
• 우선 입력 받은 가치들이 담긴 배열(@values@)을 내림차순 정렬하면 다음과 같다.

values[0]	values[1]	values[2]	values[3]	values[4]	values[5]	values[6]	values[7]	values[8]	values[9]
50000	10000	5000	1000	500	100	50	10	5	1

• 벡터 @values@의 값(@i@)이 @K(4790)@보다 작거나 같은 위치(@i <= k@)부터 계산을 해나갈 것이다.

 

단계 1 : values[3]

• 4790(@K@)를 1000(@i@ = @values[3]@)으로 나눈 후의 몫(@K / i@)은 4790 / 1000 = 4이다.
• 이것은 1000원 짜리 동전을 4번 사용했다는 뜻이다.
• @cnt@ 값을 업데이트 해준다. (@cnt = cnt + (K / i)@ = 0 + 4 = 4)
• 이제 @K@ 값을 업데이트 해준다. (@K = K - ((K / i) * i)@ = 4790 - (4 * 1000) = 790) 

 

단계 2 : values[4]

• 790(@K@)를 500(@i@ = @values[4]@)으로 나눈 후의 몫(@K / i@)은 790 / 500 = 1이다.
• 이것은 500원 짜리 동전을 1번 사용했다는 뜻이다.
• @cnt@ 값을 업데이트 해준다. (@cnt = cnt + (K / i)@ = 4 + 1 = 5)
• 이제 @K@ 값을 업데이트 해준다. (@K = K - ((K / i) * i)@ = 790 - (1 * 500) = 290) 

 

단계 3 : values[5]

• 290(@K@)를 100(@i@ = @values[5]@)으로 나눈 후의 몫(@K / i@)은 290 / 100 = 2이다.
• 이것은 100원 짜리 동전을 2번 사용했다는 뜻이다.
• @cnt@ 값을 업데이트 해준다. (@cnt = cnt + (K / i)@ = 5 + 2 = 7)
• 이제 @K@ 값을 업데이트 해준다. (@K = K - ((K / i) * i)@ = 290 - (2 * 100) = 90) 

 

단계 4 : values[6]

• 90(@K@)를 50(@i@ = @values[6]@)으로 나눈 후의 몫(@K / i@)은 90 / 50 = 1이다.
• 이것은 50원 짜리 동전을 1번 사용했다는 뜻이다.
• @cnt@ 값을 업데이트 해준다. (@cnt = cnt + (K / i)@ = 7 + 1 = 8)
• 이제 @K@ 값을 업데이트 해준다. (@K = K - ((K / i) * i)@ = 90 - (1 * 50) = 40) 

 

단계 5 : values[7]

• 40(@K@)를 10(@i@ = @values[7]@)으로 나눈 후의 몫(@K / i@)은 40 / 10 = 4이다.
• 이것은 10원 짜리 동전을 4번 사용했다는 뜻이다.
• @cnt@ 값을 업데이트 해준다. (@cnt = cnt + (K / i)@ = 8 + 4 = 12)
• 이제 @K@ 값을 업데이트 해준다. (@K = K - ((K / i) * i)@ = 40 - (4 * 10) = 0) 

 

• @K@의 값이 0이 되었으므로, @cnt@의 값은 업데이트 되지 않을 것이다.
• 최종적으로 @cnt@의 값이 이 문제의 정답이 된다.

 

코드

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

int N, K, value, cnt;
vector<int> values;

void Input() {
    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        cin >> value;
        values.push_back(value);
    }
}

int Solution(int k) {
    sort(values.begin(), values.end(), greater<int>());    // 내림차순 정렬

    for (auto i : values) {
        if (i <= k) {
            cnt += k / i;
            k -= ((k / i) * i);
        }
    }
    return cnt;
}

void Output() {
    cout << Solution(K) << '\n';
}

void Solve() {
    Input();
    Output();
}

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

    Solve();

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [그리디 알고리즘]
• 실버IV

 

그리디 알고리즘(Greedy Algorithm, 욕심쟁이 알고리즘)

• "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법
• 그리디 알고리즘은 탐욕 선택 속성(Greedy Choice Property), 최적 부분 구조(Optimal Substructure) 특성을 가지는 문제들을 해결하는 데 강점이 있다. 
  • 즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다.

 

거스름돈 문제(Minimum Coin Change Problem)

• 거스름돈 문제는 그리디 알고리즘으로 풀 수 있는 유명한 문제이다.
• 단, 동전들에 배수 관계가 성립할 때만 한정된다.
  • 대부분의 화폐는 1, 5, 10, 25, 50 등 딱 떨어지는 수치를 가지고 있기 때문에 그리디 알고리즘으로 해결된다.

 

참고 사이트

• https://namu.wiki/w/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

그리디 알고리즘 - 나무위키