BAEKJOON 1654 LANのクリップ

質問する

https://www.acmicpc.net/problem/1654

に答える

バイナリ探索を行わないとタイムアウトは避けられない.与えられたN値と同じになる前に,最大限のバイナリ探索を行い,mid値を出力すればよい.

コード#コード#

import sys
sys.stdin = open('input.txt')

K, N = map(int,input().split())

arr = [int(input()) for _ in range(K)]

start = 1
end = max(arr)

while start <= end:                                 # start가 end를 넘어서면 종료
    mid = (start + end) // 2                        # 가운데를 중심으로 양쪽 탐색
    if sum(list(map(lambda n:n//mid, arr))) >= N:   # 주어진 N과 값이 같거나 크면 start를 mind+1로 당겨옴
        start = mid+1
    else:                                           # 그렇지 않다면 마지막 지점을 당겨옴
        end = mid-1
        mid = (start+end)//2
print(mid)

結果

最初に問題を解くときはバイナリ探索アルゴリズムについて何も知らなかったので,グリッド化方式を採用した.そのため、数字が大きくなると検索数が多すぎてタイムアウトになります.その後アルゴリズムをある程度学習した後,バイナリ検索の手法を用いてアクセスしたが,このときバイナリ検索の実現には正確な理解が欠けており,最初は誤りもあった.
まだ完全に理解していないと思いますので、アルゴリズムを探索する問題をいくつか作ったほうがいいと思います.