백준: 1654 랜선 자르기

문제

1654번: 랜선 자르기

 

문제 풀이

 K개의 랜선이 있을 때, N개의 랜선을 만들고자 하는 경우 각 랜선의 길이가 최대가 되는 경우를 반환하는 문제이다. 문제의 분류와 같이, 이분 탐색을 통해 문제를 해결할 수 있다.

 

• 이분 탐색은 start, mid, end를 통해 찾고자 하는 목표를 탐색할 수 있다.
  • start 1, end는 가장 긴 랜선의 길이로 지정한다.
  • mid = (start + end) // 2
  • 주어진 랜선들을 mid로 나누고 이를 합한다.
  • 합산한 결과가 N과 비교하여 크다면 탐색 범위인 s를 1 증가시키고 작다면 e를 1 감소시킨다.
• 위와 같은 로직을 더 이상 반복할 수 없을 때까지 진행하면, 답을 찾을 수 있다.

 

코드

from sys import stdin


if __name__ == '__main__':
    k, n = map(int, stdin.readline().split())
    lan_cables = [int(stdin.readline()) for _ in range(k)]
    s, e = 1, max(lan_cables)

    while s <= e:
        m = (s + e) // 2
        make_line = sum([line // m for line in lan_cables])

        if make_line >= n:
            s = m + 1
        else:
            e = m - 1

    print(e)