[백준 11047] 동전 0

[백준 11047] 동전 0

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

문제

준규가 가지고 있는 동전은 총 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

• 문제 이해하기

동전의 종류를 정하고, 원하는 금액 총합을 입력한다.동전 종류만큼 오름차순으로 동전의 가치를 입력하면, 내가 입력한 금액 총합을 갖고 있는 동전 개수의 최소값을 구하는 문제다.
즉 4510원이 총합일 때, 10원, 100원, 500원, 1000원, 5000원 총 5개의 동전 종류가 있다면?최소 동전은 1000원 4개, 500원 1개, 10원 1개로 6개가 출력되어야 한다.

• 계획 및 문제해결

이는 그리디 알고리즘을 통해 해결이 가능하다. 그리디 알고리즘이란, 현재 상황에 가장 좋다고 생각하는 것을 선택하면서 답을 구해나가는 알고리즘을 말한다. 즉, 가장 큰 가치의 동전부터 현재 금액과 비교해나가면 될 것이다.

위에서 예를 든 4510원과 10원, 100원, 500원, 1000원, 5000원으로 총 5가지 동전 종류를 만들었다고 생각해보자.

그렇다면, 현재 n은 5, k는 4510으로 내가 입력을 해둔 상태다.

int n, k; // 동전 종류 수와 가치 합 선언
 
cin >> n >> k;

5개의 동전의 가치를 저장하기 위해서, vector를 이용했다.

#include <vector>
 
vector<int> v(n);
 
for (int i = 0; i < n; i++) {
    cin >> v[i]; // 동전의 가치 값 입력
}

벡터 v의 값에 오름차순으로 차례대로 동전의 가치를 저장시킨다.

현재 저장상태는 다음과 같을 것이다.

v[0] = 10
v[1] = 100
v[2] = 500
v[3] = 1000
v[4] = 5000

최소 동전의 수를 저장할 cnt 변수를 만들고, 저장된 v의 동전 가치를 이용해 구해야한다.우리는 '최소'개수를 구해야하므로, 가장 큰 가치를 지닌 동전부터 몇개가 필요한 지 접근하는 것이 바람직하다.이러한 현재 상황에서 최선의 방법을 선택하는 접근이 '그리디 알고리즘'을 말한다.
k=4510보다 큰 가치를 지닌 동전은 사용할 수 없다.따라서 k값에 현재 지닌 v를 가장 나중에 들어온 데이터부터 '나눗셈'을 활용해 cnt에 저장하는 방법을 이용해보자.
1. k에 가장 나중에 들어온 데이터인 v[4]를 나누면 0이 된다. ( 4510 / 5000 ) 즉, 사용할 수 없는 동전이다. 0을 cnt에 더한다.2. k를 v[3]으로 나눈다. ( 4510 / 1000 ) 결과는 4다. 즉, 1000원 동전을 4개 사용할 수 있다는 뜻이다. 4를 cnt에 더한다.3. 이제 1000원 동전 4개를 사용하고 남은 k 금액으로 다음 동전 가치의 수를 구해야 한다. 따라서 k를 v[3]으로 나눈 나머지 값을 가져오자. ( k % v[3] )4. 이와 같은 진행을 v[0]까지 반복
for문을 통해서 위의 과정을 끝내면, 우리가 필요한 최소 동전의 개수가 cnt에 저장되어 있다. 이를 출력해주면 끝난다.

int cnt = 0; // 사용된 동전 수 저장할 cnt 선언
 
for (int i = n - 1; i >= 0; i--) { // 오름차순이므로 가장 마지막에 들어온 값부터
    cnt += k / v[i];
    k %= v[i];
}
 
cout << cnt << endl;

• 전체 소스 코드

#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    int n, k; // 동전 종류 수와 가치 합 선언
 
    cin >> n >> k;
 
    vector<int> v(n);
 
    for (int i = 0; i < n; i++) {
        cin >> v[i]; // 동전의 가치 값 입력
    }
 
    int cnt = 0; // 사용된 동전 수 저장할 cnt 선언
 
    for (int i = n - 1; i >= 0; i--) { // 오름차순이므로 가장 마지막에 들어온 값부터
        cnt += k / v[i];
        k %= v[i];
    }
 
    cout << cnt << endl;
 
}