[백준] 1654번 랜선 자르기 (Python 파이썬)

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

1654번: 랜선 자르기

문제는 내가 현재 가지고 있는 서로 다른 길이의 랜선들을 잘라서 동일한 길이의 새로운 랜선을 여러개 만드는 것이다.

내가 가지고 있는 랜선의 개수 K와 새로 만들 랜선의 개수 N을 입력받는다.

예를 들어 K=4, N=11 이라면 4개의 긴 랜선을 잘라 11개의 짧은 랜선을 만드는 것이다.

이 때, 11개를 만들 수 있는 랜선의 최대 길이를 구하면 된다.

즉, 11개를 만들기 위해서 랜선을 얼마나 잘라야 하는지를 알면 된다.

 

정답으로 200을 출력한다면 가지고 있는 4개의 랜선으로 새로운 랜선 11개 만들 때 이 새로운 랜선의 최댓값이 200이 된다는 말이다.

 

문제에서 주어진 랜선의 길이는 2^31 - 1보다 작거나 같은 자연수 이기 때문에 절대 앞에서 부터 하나씩 값을 검사하는 순차탐색으로는 시간내에 해결할 수 없다.

 

그래서 이진탐색(Binary Search)을 이용하였다.

내가 가지고 있는 랜선의 길이의 합을 end값으로, 0을 start값으로 설정하여 이 두 값의 절반을 mid값으로 설정한 후, 탐색을 하면 된다. 0과 1600이라면 800부터 검사를 시작하여 문제를 해결해 나가면 된다.

 

순차탐색보다 훨씬 시간도 줄어들고, 시간 초과 문제도 해결할 수 있다.

 

코드는 다음과 같다.

k, n = map(int, input().split())
lan = []

maxcm = 0


def binary_search(array, target, start, end):
    while start <= end:
        moksum = 0
        mid = (start + end) // 2
        if mid == 0:
            return start        # 0값을 나누는 예외상황 처리
        for i in array:
            mok = i // mid
            moksum += mok
        if moksum < target:  # 개수를 더 늘려야 하므로 길이를 줄이자
            end = mid - 1
        elif moksum >= target:  # 개수를 더 줄일 수 있으므로 길이를 늘리자
            start = mid + 1

    return end


for i in range(k):
    lan.append(int(input()))

lansum = sum(lan)  # 입력받은 모든 랜선 길이의 합


result = binary_search(lan, n, 0, lansum) # 길이 배열, 만들어야 하는 랜선수, 시작값, 끝값
print(result)

 

https://github.com/HongEunho

HongEunho - Overview

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !