[11047]硬貨0

[11047]硬貨0

質問する

ジュンギュが持っているコインは全部でN種類で、どれもたくさんあります.
硬貨を適当に使って、その価値の和をKにします.必要なコインの数の最大値を求めるプログラムを作成してください.

入力

第1行はNとKを与える.(1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
2行目から、N行目では昇順にコインの価値Aiが与えられる.(1≦Ai≦100000,A 1=1,i≧2の場合、AiはAi-1の倍数)

しゅつりょく

Kドルを作るのに必要なコインの数の最大値を1行目に出力します.

コード#コード#

#include <iostream>

using namespace std;

/* 조건 */
#define MAX_N 11
#define MAX_K 100000001

/* 변수 */
int N, K;
int coin[MAX_N];
int count = 0;

/* 함수 */

int main() {
    /* 입력 */
    cin >> N >> K;
    for(int i = 0; i < N; i++) {
        cin >> coin[i];
    }

    /* 풀이 */
    for(int i = N-1; i >= 0; i--) {
        if(K == 0) break;
        if(K >= coin[i]) {
            count += K / coin[i];
            K %= coin[i];
        }
    }

    /* 출력 */
    cout << count;
}

に答える

このコインの問題は簡単で、例外のない問題で、総価格を最大の単位から計算すれば、コインの個数を数えることができます.
(例外)
この問題はgreedyアルゴリズムの代表的な問題であり,greedyアルゴリズムを適用する場合にも最適である.
実際、以下の状況はこの問題とは異なる.
1元7元10元で15元作ります
出力結果-->10元*1個+1元*5個=6個
実際正解-->7元*2個+1元*1個=3個
コイン0の問題は、次の小さな数字が1/2以下だかららしい.
(推測、不確実、単純な思考)

ソース

白駿[1047]硬貨0
https://www.acmicpc.net/problem/11047