[baekjoon]백준 1654번 : 랜선 자르기 (by python 파이썬) 이분탐색

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

1654번: 랜선 자르기

 

code

import sys
input = sys.stdin.readline

k, n = map(int,input().split())
l = []
for i in range(k):
    lan = int(input())
    l.append(lan)

start, end = 1, max(l)

while start <= end:
    mid = (start+end)//2
    lines = 0
    for i in l:
        lines += i //mid
    if lines >= n:
        start = mid + 1
    else:
        end = mid - 1
    
print(end)

 

이번 문제는 이분 탐색을 활용하는 문제다.

 

이분 탐색을 사용하지 않고 순차 탐색을 한다면 시간초과에 걸리게 된다.

 

이분탐색은 탐색범위를 절반씩 줄여가며 탐색하기 때문에 시간복잡도 O(log n) 으로 끝낼수 있다.

 

 

이분탐색의 구현 방법은 간단하다.

1. mid값(중앙값)을 찾는다.

2. mid값과 원하는 값과 비교한다.

3. 원하는 값이 나올때 까지 반복한다.

(원하는 값보다 크면 start를 mid +1로 옮기고,

원하는 값보다 작으면 end 를 mid -1로 옮긴다)