[Python] 백준 알고리즘 #1654 랜선 자르기

문제풀이 

 

랜선의 길이를 K개에서 N개 이상으로 만들 수 있는 가장 큰 랜선의 길이를 구해야 한다. 

 

길이를 1씩 늘리거나 줄이는 완전 탐색 방법은 시간적으로 비효율적일 수 있다. 이를 보완한 알고리즘이 '이분 탐색(Binary Search)' 알고리즘이다. 

 

정렬된 값이 나열되었을 때, 특정 값을 O(logN)의 시간 복잡도를 갖고 찾을 수 있다는 장점이 있다.

 

먼저 코드를 작성하기 전 이분탐색을 이용하여 어떻게 구현할지 생각해보자. 

 

기준이 되는 이분탐색 코드는 다음과 같다.

 

def bi_search(target, A):
    start = 0
    end = len(A)-1

    while start <= end:
        mid = (start+end)//2

        if A[mid] == target:
            return 1
        elif A[mid] < target:
            start = mid+1
        else:
            end = mid-1
    return 0

 

1. 이분 탐색을 하는 중, 잘라야 하는 랜선의 길이를 정하고 잘랐을 때, 총랜선의 개수가 N 보다 작을 경우, 잘라야 하는 랜선의 길이 기준을 더 작게 해서 잘린 랜선의 개수를 늘려준다. 이때 이분 탐색에서는 end 값을 mid-1 값으로 변경해준다. 

 

2. 이분 탐색을 하는 중, 잘라야 하는 랜선의 길이를 정하고 잘랐을 때, 총 랜선의 개수가 N과 같거나 클 경우 탐색을 멈추는 것이 아니라, 잘라야 하는 랜선의 길이가 최대라고 보장되지 않기 때문에, 잘라야 하는 랜선의 길이 기준을 더 크게 해서 잘린 랜선의 개수를 줄여준다.  이때 start 값을 mid+1 값으로 변경해준다.

 

소스코드

import sys
input = sys.stdin.readline

K, N = map(int, input().split())

lines = [int(input()) for _ in range(K)] 

start, end = 1, max(lines)
result = 0
while start <= end:
    mid = (start+end)//2

    cut_sum = sum([line//mid for line in lines])
    #print(cut_sum)

    if cut_sum >= N: # 자른 랜선의 갯수가 N보다 크거나 같을 경우
        start = mid+1 # 자를 랜선의 기준을 더 크게 잡아서 랜선의 갯수를 줄여줌
        result = mid # 가장 마지막에 나온 mid 값이 정답
    else: #자른 랜선의 갯수가 N보다 작을 경우
        end = mid-1 # 더 작게 잡아서 랜선의 갯수를 늘려줌

print(result)

 

www.acmicpc.net/problem/1654

1654번: 랜선 자르기