[イコール]グリディ-冒険者公会

🔔 質問する

ある村にはN人の冒険者がいる.冒険者組合はN人の冒険者を対象に「恐怖度」を測定したが、「恐怖度」の高い冒険者は恐怖を感じやすく、危険な状況では正しく対応できなかった.冒険者組合の職人である東彬は、安全に冒険者グループを結成するため、恐怖度Xの冒険者はX人以上の冒険者グループに参加しなければ旅行を出発できないと規定している.東彬は最大何人の冒険者グループを作成できるか知りたい.東彬にN名の冒険者に関する情報を提供した場合、旅行可能なグループ数の最高値を求めるプログラムを作成してください.△何人かの冒険者が村に残ることができるので、すべての冒険者を特定のグループに置く必要はありません.

入力

行目冒険者の数N.(1<=N<=100,000)

の2行目は、各冒険者の恐怖度の値N以下の自然数を与え、各自然数はスペースで区切られている.

しゅつりょく

トラベルグループ数の最値を出力します.

🎯 解答方法

まず恐怖度を基準に昇順で並べ替えました.その後、恐怖度が最も低い冒険者から一つ一つ確認し、グループ内の冒険者数を算出することができる.現在のグループの冒険者数が現在確認されている恐怖度以上であれば、グループ化できます.すなわち、「現在の組合せに含まれる冒険者の数」が「現在確認された恐怖度」以上である場合、これを組合せに設定することができる.

💻 Pythonコード

n = int(input())
values = sorted(list(map(int, input().split())))

group = 0 # 결성된 그룹 수

temp = 0 # 현재 멤버 수
for i in values:
    temp += 1
    if temp >= i:
        group += 1
        temp = 0

print(group)