[백준 1654번] 이분탐색 ( Binary Search)

 

- 처음 짠 코드

import sys
k, n = map(int,sys.stdin.readline().split())
lansun = []

for i in range(k):
    lansun.append(int(sys.stdin.readline()))

count = max(lansun)
while True:
    a = 0
    for i in range(k):
        a += lansun[i] // count
    if a>=n:
        break
    else:
        count -= 1
print(count)

처음에는 lansun리스트에서 min을 골라 1씩 빼가며 내려가면 원하는 값을 찾을 수 있을거라 생각했다.

-> 시간초과 -> input을 sys.stdin.readline()으로 바꾸고 list comprehension으로 만들어 보기도 함

하지만 해결되지 않았고 구글링을 통해 '이분탐색' 알고리즘을 찾게 되었다. 

 

쉽게 말하자면 전체 리스트에 나열되어 있는 원소들을 책의 페이지라고 생각하면 중간을 펴보고 작은지 큰지를 판단, 또 중간을 펴보고 작은지 큰지를 판단하는 식이다. 확실히 책의 페이지가 커지면 커질수록 원하는 페이지를 찾는데에 있어 한페이씩 비교를 해보는 것보다 빠르게 판단할 수 있겠다.

 

- 최종적으로 완성한 코드

import sys
k, n = map(int,sys.stdin.readline().split())
lansun = [int(sys.stdin.readline()) for _ in range(k)]

start, end = 1, max(lansun)

while start <= end:
    mid = (start + end) // 2   
    a = sum([i//mid for i in lansun])
        
    if a >= n:
        start = mid + 1
    else:
        end = mid -1
print(end)

 

오늘은 2021년의 마지막 날이다. 내년에는 조금 더 나은 사람이 될 수 있도록 노력해야지..!!