BOJ 1654: 랜선 자르기 [Python 3]

오늘의 문제는 랜선 자르기이다.

 

이 문제의 특징은, 랜선의 길이가 2의 31제곱-1까지 커질 수 있기 때문에, for문을 1부터 2의 31제곱-1까지 돌리면 시간 초과가 발생한다.

그렇기에 다른 방법을 사용해야 하는데, 이분 탐색을 통해 구현해보았다.

 

정답 코드이다.

k,n=map(int,input().split())
data=[]
for _ in range(k):
    data.append(int(input()))
data.sort()
minNum=1
maxNum=max(data)
while minNum<=maxNum:
    num=0
    mid=(minNum+maxNum)//2
    for i in data:
        num+=i//mid
    if num>=n:
        minNum=mid+1
    else:
        maxNum=mid-1
print(maxNum)

먼저 값들을 input 받고, 1부터 input 중 제일 큰 값 사이에 mid를 둔다.

이제 그 mid로 data에 있는 모든 element를 나눠서 몫을 더했을 때,

몫이 필요한 랜선의 길이보다 많으면 랜선의 크기를 키워야 하기에 범위를 mid에서 max로 바꾼다.

만약 반대로 랜선의 길이가 부족하면, 랜선의 크기를 잘게 줄여야 하기에, 범위를 min에서 mid로 바꾼다.

 

이런 식으로 계속 진행하고 최댓값을 print하면 된다.