[C++] 백준 11047 동전 0

 

 www.acmicpc.net/problem/11047

11047번: 동전 0

1. 서론

이 문제는 그리디 알고리즘으로 풀 수 있다.

그리디 알고리즘이란 매 순간 최적의 방법을 선택하는 것이다.

결과적으로 최적의 방법은 아닐지 몰라도 고를 수 있는 선택지 중에서 가장 최적의 방법을 고르는 것이다.

 

2. 문제풀이

N종류의 동전을 조합해서 그 합을 K로 만든다. 이때 필요한 동전 개수의 최솟값을 구하는 문제이다.

예제로 예를 들자면 10종류의 동전이 있고 4200원을 만들어야 한다. 

동전의 종류는 1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000이다.

그렇다면 최적의 방법은 1000 * 4 + 100 * 2이다. 즉, 6개의 동전이 필요한 것이다. 

 

최적의 조합으로 문제를 풀기 위해서는 동전의 종류 중에서 K와 가장 가까운 값의 동전부터 선택해서 조합을 생각해야 한다.

500원의 조합으로 100원짜리 5개가 아니라 500원짜리 1개를 골라야 하는 것이다.

따라서 동전이 작은 단위부터 큰 단위 순으로 입력되기 때문에 역순으로 큰 단위의 동전부터 값을 체크하며 카운트를 해주면 문제를 풀 수 있다.

 

3. 코드 설명

#include <stdio.h>
#include <iostream>
using namespace std;
int main()
{
    int n, k, a[10], i, cnt = 0;

    cin >> n >> k;
    
    for (i = 0; i < n; i++)
       cin >> a[i];

    for (i = n - 1; i >= 0; i--)
    {
        if (a[i] <= k && k != 0)
        {
           cnt += k / a[i];
           k %= a[i];
        }

    }

   cout << cnt << endl;
}

 

종류의 값을 n, 동전의 합을 k, 동전의 종류를 배열 a로 받고, 배열을 역순으로 검사한다.

역순으로 검사하는 이유는 뒤에 입력된 값이 더 큰 값이기 때문에 큰 값을 먼저 찾아내기 위해서이다.

배열을 역순으로 검사하면서 동전의 합 k와 비교했을 때, 같거나 작은 것을 만나면 cnt로 동전의 개수를 저장한다.