11047번

11047번 - 동전 0

그리디 알고리즘 공부중.. 예제 문제여서 풀었다.

그리디 라는 것을 알고 푸니까..

근데 그 정당성 증명을 어떻게 해야할 지 잘 모르겠다.

(추가)

내가 한 정당성 증명 - 맞게 한 것인지는 모르겠다.

만들어야하는 K보다 작은, 가장 큰 동전을 CoinMax 라고 하자.

정답 S의 최적해 중 CoinMax 를 선택하지 않는 답이 존재한다고 하자.

그렇다면 문제에서 나와있듯이, 동전들은 모두 배수 관계에 있기 때문에, S의 답에서 적절한 합을 통하여 CoinMax를 만들 수 있습니다.

따라서 새로 만든 목록도 최적해 중 하나가 됩니다. 따라서 항상 CoinMax를 포함하는 최적해가 존재합니다.

##질문게시판##

이렇게 쉽게... 내 말을 요약..

<정답 코드>

#include<iostream>
#include<vector>
using namespace std;
 
int main()
{
 
    int N, K, ans = 0;
    vector<int> coin;
 
    cin >> N >> K;
 
    for (int i = 0; i < N; i++)
    {
        int tmp;
        cin >> tmp;
        coin.push_back(tmp);
    }
 
    reverse(coin.begin(), coin.end());
 
    bool finish = false;
    int cnt = 0;
    while (!finish)
    {
        if (coin[cnt] <= K)
        {
            K -= coin[cnt];
            ans += 1;
        }
        else
        {
            cnt += 1;
        }
 
        if (K == 0)
        {
            finish = true;
        }
    }
 
    cout << ans << endl;
 
    return 0;
}