백준 1654 - 랜선 자르기 (Python)

문제

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

1654번: 랜선 자르기

풀이

#가장 단순한 풀이법 - 시간초과 오답
k,n = map(int,input().split())
l = [int(input()) for _ in range(k)]

m= 0
for i in range(1,max(l)+1):
    cnt = 0
    for j in l:
        cnt += j//i
    if cnt >= n:
        m = i
print(m)

가장 단순하게 생각 할 수 있는 방법은 위와 같다.

1 과 입력받은 최대길이 사이의 모든 숫자를 돌아가면서 나눠지는 개수를 판단하고 n을 넘을 경우 최댓값을 갱신 해주면서 답을 도출하는 방식이다.

하지만 모든 길이를 탐색하니까 시간초과로 오답을 받게 되었다.

 

시간을 줄이기 위해 이분탐색을 활용하는 코드로 바꾸어 주었다.

#이분탐색 활용 - 정답
k,n = map(int,input().split())
l = [int(input()) for _ in range(k)]

start, end = 1, max(l)+1
while True:
    if end - start <2:
        break

    mid = start + (end - start)//2   
    cnt = 0
    for j in l:
        cnt += j//mid

    if cnt >= n:
        start = mid
    else:
        end = mid
print(start)

 

start를 1로, end를 가장 긴 입력 + 1로 정해 둔 후

중앙값을 이용해 개수를 구했을 때 n이 넘으면 다음 탐색 범위를 mid~end 로 바꾼다.

반대로 n이 넘지 않으면 다음 탐색 범위를 start ~ mid 로 바꾼다.

이렇게 범위를 좁혀 나가다 보면 구간의 길이가 1 또는 0이 되고 이때 start의 값이 정답이 된다.