[BOJ/伯俊]11047(コイン0)C++

テーマ

greedy

アイデア

銅貨のような質問ですが、実は解題方法が全然違います…!
はこの条件のためです!
この問題には排水の条件があり、グリディで簡単に解くことができます.

ソースコード

/*
boj11047.cpp
2021-01-08 정설희
동전 0
*/

#include <bits/stdc++.h>
using namespace std;
int arr[11];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, k; cin >> n >> k;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    for (int i = n; i > 0; i--) {
        cnt += k / arr[i];
        k %= arr[i];
        if (k == 0)
            break;
    }
    cout << cnt;
}

学識

DP vs Greedy

ダイナミックプログラミング
J出発前に交通信号、交通状況、公共交通、街道を知る方法
長所:すべての可能性を考えることを決める.したがって,動的プログラミングの結果は常に最適な結果を得ることができる.
欠点:多くの意思決定順序が生成されます.そのため、ダイナミックプログラミングを実現するには大きなメモリスペースが必要です.👉 おおよその方法
グレースケールアルゴリズム
Pまず出発当時の状況に応じて最速で進む方法
利点:より多くの問題に応用できる最も簡単な設計方法です.
短所:段階別に行い、各段階で現在の状態で最適と判断する決定を下す.このとき,全体が最適かどうかをチェックせず,現在の状態の観点からのみ最適と判断する決定を下す.すなわち,グリディアルゴリズムは問題に基づいて最適解を求めることができ,そうでなくてもよい.