[99클럽 코테 스터디 2일차 TIL] 이분 탐색 - 백준 1654번 문제 (랜선 자르기)

 

 

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

 

백준 1654번 문제

 

풀이

이분 탐색을 활용하는 방법

이진 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘 입니다. 따라서 sort() 메서드를 사용하여 정렬을 우선 해줘야 합니다. 그리고 보통 변수 3개 (start, mid, end)를 사용하여 탐색하게 됩니다.

이분 탐색을 사용할 경우 시간 복잡도는 O(logN)입니다. 단계마다 탐색 범위를 반으로 나누는 것과 동일하므로 O(logN)이라는 시간 복잡도를 가지게 됩니다. 

import sys

read = sys.stdin.readline
K, N = map(int, read().split())
data = list()
for i in range(K):
    data.append(int(read()))
start, end = 1, max(data)

while start <= end:
    mid = (start + end) // 2
    lines = sum(i // mid for i in data)
    if lines >= N:
        start = mid +1
    else:
        end = mid -1
print(end)

 

TIL

1일차 때 이분 탐색을 활용한 풀이를 진행을 했었기 때문에 문제를 보고 바로 이분 탐색을 적용하여 해결을 했습니다.

한번 더 이분 탐색 알고리즘을 다른 문제에 적용해서 풀어봄으로써 이분 탐색이라는 알고리즘을 조금 더 이해를 하게 되었던 기회가 되었습니다.

 

이 외에도 다른 방법이 있다면 정보를 공유해주시면 감사하겠습니다.