[백준] 1654 랜선 자르기 - Python

문제

1654번: 랜선 자르기

1654번: 랜선 자르기

위 문제는 주어진 k개의 랜선들을 잘라서 최대 N개가 되도록 만들어 줄 때, 자른 길이의 최댓값을 구해주는 문제입니다.

이를 해결하기 위해서는 이분 탐색을 활용해야 하는데요.

(이분 탐색은 “~와 ~사이에 답이 있다.”의 경우에 사용하면 해결에 도움이 될 수 있습니다.)

이분 탐색을 활용하기 위해선 범위를 지정해주어야 하는데, 위 문제의 경우에는 1 ~ (K개의 랜선들 중 최댓값) 까지 범위를 두고 좁혀 나가면서 N개로 자를 수 있는 랜선 길이의 최댓값을 구해주면 됩니다.

Python

def cnt(nums, mid): # (1)
    cnt = 0
    for i in nums:
        cnt += i // mid
    return cnt

def binary_search(nums, s, e, n): # (2)
    if s > e:
        return e
    mid = (s + e) // 2

    if cnt(nums, mid) >= n:  # case : 타겟 목표와 우리가 자른 갯수가 크거나 같음
        s = mid + 1
        return binary_search(nums, s, e, n)
    else:  # cnt <n
        e = mid - 1
        return binary_search(nums, s, e, n)

k, n = map(int, input().split())
line = [int(input()) for i in range(k)]
print(binary_search(line, 1, max(line), n))

1. cnt 함수는 리스트에 저장한 각 랜선들을 mid값으로 나눈 값들을 누적하여 리턴해주는 함수입니다. 즉, mid 값으로 나눈 값들을 더해준다는 것은 자른 랜선의 갯수를 누적하여 만들어 낼 수 있는 랜선의 최대 갯수를 반환해 줍니다.
2. 함수명에도 나타나 있듯이 이분 탐색을 진행하는 함수입니다.

• 잘린 랜선의 길이가 문제에서 주어진 N보다 크거나 같으면, 크기가 더 큰 랜선으로 잘라주어 잘린 갯수를 줄일 수 있으므로 시작 범위를 더 크게 설정합니다.
• 잘린 랜선의 길이가 문제에서 주어진 N보다 작으면, 너무 크게 자른 것이므로 끝 범위를 더 작게 설정해 줍니다.