異なるアルゴリズムタイプのエクスポート問題:Griddy

💻 4.作成できない金額

難易度🖤🤍🤍 | プール30分|タイムアウト1秒|メモリ制限128 MB|K大会出力

📌2021、01/03コード作成

# 입력
n = int(input())
data = list(map(int, input().split()))
data.sort(reverse=True) # 내림차순으로 정렬

# 알고리즘
ret = 1 # 1로 초기화
stop = False
while not stop:
    temp = ret # temp에 ret 값 할당

    # 내림차순으로 정렬된 data 순회하면서 ret값 만들 수 있는지 확인
    for x in data:
        if temp//x > 0: # 몫이 0보다 크면
            temp -= x # 그 값을 temp에서 뺀다
        else:
            continue
    # temp가 0이라면 ret값 만들 수 있다는 것
    if temp == 0:
        ret += 1 # 다음 테스트를 위해 + 1
    else:
        stop = True

# 출력
print(ret)

💭 アイデア

アルゴリズムが作られていますが、なぜか分かりません…!

🤓 問題の説明

01

これはソートされた階調アルゴリズムで解決できる問題である.問題を正しく解決する方法を考えるには、十分な考慮が必要であるため、読者がグレディアルゴリズムに慣れていないと、問題を解決するのは難しい.
問題解決の構想は以下の通りである.コインに関する情報が得られると、通貨単位を基準に昇順に並べられます.次に、1から順に特定の金額を作成できるかどうかを確認します.
1からtarget-1までのすべての金額を作成できると仮定します.私たちは通貨単位が小さい順にコインを確認し、現在確認しているコインでtarget金額を作ることができるかどうかを確認するだけです.target金額を作成できる場合は、target値を更新(増加)する方法を使用します.
基本的に、グリディアルゴリズムは、現在の状態で毎回最もよく見えるアルゴリズムだけを選択するアルゴリズムです.具体的には、現在のステータスは「1からtarget-1までのすべての金額を作成できます」です.この場合、毎回targetを作成できる金額(現在確認されている硬貨単位がtargetを下回っているか)をチェックします.対応する金額を作成できる場合は、targetの値を更新(現在のステータスを更新)するだけです.

02

例えばコインが3つありますが、各通貨の単位は1、2、3です.
では、1から6までのすべての金額を生成することができます.

1元:1

2元:2

3元:3

4元:1+3

5元:2+3

6元:1+2+3

そして金額7もできるかどうか確認してみましょう.このとき、通貨単位5の硬貨が新たに与えられたと仮定します.現在は通貨単位5の硬貨が与えられているので、1から11までのすべての金額を生み出すことができます.もちろん自動で金額7が成立します.

1元:1

2元:2

3元:3

4元:1+3

5元:5

6元:5+1

7元:5+2

8元:5+3

9元:5+3+1

10元:2+3+5

11元:1+2+3+5

その後、金額12も作成できることを確認することができます.これは一つの方法です.このとき,新たに貨幣単位13の硬貨が与えられたとする.この場合、金額12を作成する方法はありません.だからこの場合の正解は12です.

03

別の例を見てみましょう.今回は段階的に問題解決の過程を紹介します.コインが4つある場合は、通貨単位はそれぞれ1,2,3,8と言ってみましょう.

当初はtarget=1に設定されており、金額1が作成できることを確認します.

target=1.私たちは通貨単位が1のコインを持っています.このコインで金額1を作ることができます.次にtarget=1+1=2で更新する.(1まで作成可能なすべての金額に相当)

target=2.私たちは通貨単位のコインを持っています.したがってtarget=2+2=4となる.(3まで作成可能なすべての金額に相当)

target=4.私たちは通貨単位が3の硬貨を持っています.したがってtarget=4+3=7となります.(6まで作成可能なすべての金額に相当)

target=7.私たちはこれより大きい、通貨単位が8のコインを持っています.したがって、金額7を作成する方法はありません.したがって、正解は7です.

この原理を用いて,硬貨を単純に貨幣単位で並べ替え,次いで貨幣単位の小さい硬貨から逐次確認しながらtarget変数を更新する方法で最適解を計算することができる.

04

グリディのアルゴリズムタイプを何度も解いてみると解法が思い浮かぶのですが、グリディのアルゴリズムが熟練していないと分かりにくい問題です.そこで、この問題が解決しにくい場合は、Griddyアルゴリズムタイプの問題に触れてみましょう.

ちなみに、この問題は前の理論部分で議論した「お金を探す」問題とは異なる.お金を探す問題は、各通貨単位に無限のコインが存在すると仮定し、ここでコインの数は限られている.

🤓 回答例

n = int(input())
data = list(map(int, input().split()))
data.sort()

target = 1
for x in data:
    # 만들 수 없는 금액을 찾았을 때 반복 종료
    if target < x:
        break
    target += x

# 만들 수 없는 금액 출력
print(target)

🤔 コメント

難しいです.

私はかすかに解説を理解しましたが、私が作ったアルゴリズムは最終的に正しいのか間違っているのか、まだよく検証できません...

次は努力して理解した痕跡です.

targetの意味は「次のコインを考えると、少なくともこの金額を作ることができます!」そういう意味です.硬貨が昇順に配列されていると仮定するため、iの1番目の硬貨の後ろのi+1個の硬貨はiの1番目の硬貨の価値に等しいか、またはそれ以上である.したがって、targetにcurrent valueを追加します.

なので、最初の硬貨からi+1個硬貨までの和は最小のtargetだろうな~という仮説とともにi+1個硬貨のcurrent valueを見る.この場合、current valueがtargetより大きい場合、targetはいくら作成できません.つまり、これは創造できない最低金額です.