[BOJ/C++] 11047 동전 0

그리디 알고리즘을 이용해 문제를 해결할 수 있습니다.

그리디 알고리즘

현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘

• DP보다 구현하기 쉽고 시간 복잡도가 우수하다
• 항상 최적의 해를 보장하지 못하다
• 그리디 알고리즘을 사용하기 전에 논리 유무를 충분히 살펴야 한다

그리디 알고리즘의 핵심 이론

1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
2. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다

목표 금액을 동전 개수를 최소로 하며 채우는 문제로 가격이 큰 동전부터 차례로 사용하면 됩니다.

// boj s4 11047
// 동전 0
#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

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

    int N, K;
    cin >> N >> K;

    vector<int> v(N);

    for(int i=0; i<N; i++)
    {
        cin >> v[i];
    }
    
    int count=0;
    for(int i=N-1; i>=0; i--)
    {
        if(K==0)
            break;

        if(K>=v[i])
        {
            count+=(K/v[i]);
            K=K%v[i];
        }
    }

    cout << count;

    return 0;
}