Algorithm/programmer/二分探索/level 3/入国審査(Python使用)

2795 ワード
アルゴリズム問題 バイナリナビゲーション programmers にぶんたんさく テキストリンク

📖 質問する



📝 解法


  制限事項の中の最値から分かるように,線形探索は決して制限時間内に問題を解決することはできない.バイナリナビゲーションを使用!
取得したい値:すべての人が審査を受けるのに要する時間の最高値
  全員が最長時間の審査台で審査(max(times)*n)を受けるのは最悪の場合であるため、これを終了値とし、開始値を簡単に0とする.
  ❗注目すべきは、バイナリ検索の場合、私が探している値が得られると、この値が正解になりますが、この問題の場合は、「ベスト値」を探すので、条件を満たす値が得られたとしても、より小さな数で条件を満たすかどうかの値を見つけることです.

パスワード

def solution(n, times):
    answer = 0
    # 시작값(i)과 끝값(j) 설정
    i,j = 0, max(times) * n
    
    # 이진 탐색 시작
    while i <= j:
        m = (i + j) // 2
        # tmp_n : m분동안 심사를 받을 수 있는 사람의 수를 담는다.
        tmp_n = 0
        for time in times:
            tmp_n += (m//time)
        # m분동안 심사를 받을 수 있는 사람 수가 n보다 크거나 같다면(조건 만족)
        if n <= tmp_n:
            answer = m
            j = m - 1
        else:
            i = m + 1
    return answer
貪欲法と最小コスト成長ツリー(MST)
Spring実習1-2(掲示板)