BOJ #1654 랜선 자르기

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 1654. 랜선 자르기

문제 풀이

단순 탐색이 아니라 이진 탐색의 Upper Bound를 다루는 문제다. 이진 탐색의 조금 고난도 문제는 Bound 문제와 탐색할 수 있는 형태의 문제로 분해하는 과정으로 이루어지는 듯하다. 얻을 수 있는 랜선의 개수를 카운트 하는 함수는 $O(n)$이겠지만 자르는 랜선 간격을 탐색하는 횟수는 이진 탐색을 적용하여 $O(log\ n)$ 내에 발견해야 $O(nlog\ n)$에 해결이 가능하다.

얻을 수 있는 랜선의 최대 길이를 구해야 한다. 여러개라도 1개만 요구하면 갖고 있는 랜선들 중 가장 긴 랜선을 주어야 하므로 최대 시작 간격은 max(보유 랜선 길이)이고 최소 시작 간격은 역시 1이다.

• 보유하고 있는 랜선의 개수, 요구 랜선 개수, 랜선 목록을 입력받는다.

• 랜선 배열들 중 최대값을 추출한다.

• 얻을 수 있는 랜선 개수를 계산하는 함수를 작성한다. (각 랜선에 대해 탐색 간격으로 나눈 몫이다.)

• 이진 탐색 알고리즘을 수행한다. (최소 간격이 최대 간격과 동일해질 때까지)

  얻고사 하는 전선의 길이가 가능한 최대 길이이므로 최소 간격의 조정이 필요한 경우에 등호를 넣고 버퍼에 현재 탐색 간격을 저장하여 종결 상황을 준비한다.

• 종료 후 버퍼에 저장된 길이 반환

python 코드

import sys
input = sys.stdin.readline

K, N = map(int, input().split())
arr = []
for _ in range(K):
    arr.append(int(input()))

def search(arr, N):
    def get_lines(dist):
        result = 0
        for a in arr:
            result += a // dist
        return result
    min_dist, max_dist = 1, max(arr)
    sol = 1
    while min_dist <= max_dist:
        mid_dist = min_dist + (max_dist - min_dist) // 2
        cnt = get_lines(mid_dist)
        if cnt >= N:
            min_dist = mid_dist + 1
            sol = mid_dist
        elif cnt < N:
            max_dist = mid_dist - 1
    return sol

print(search(arr, N))