1654번: 랜선 자르기 [Python]

일단 되게는 하자

import sys

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

max = 0
min = 1

for i in range(k):
    tmp = int(sys.stdin.readline())
    if tmp > max:
        max = tmp
    v.append(tmp)

max += 1

while(min < max):
    sum = 0
    mid = min + ((max - min) // 2)
    for i in range(len(v)):
        sum += v[i] // mid

    if sum == n:
        tmpResult = mid
    elif sum < n:
        max = mid
    else:
        min = mid + 1

if sum < n:
    print(tmpResult)
else:
    print(mid)

2진 탐색을 이용했다. 길이를 이진 탐색으로 특정하고, 이를 for 문으로 일일이 랜선을 나누어보는 작업이다. 그래서 시간 복잡도는 NlogN 이다.

특이한 점은 정답이 될 수 있는 여러 값 중 가장 큰 값을 구하는 것이다. Upper Bound 개념을 이용하면 될 것 같다.

while 문이 동작하는 중에 mid 값이 정답 중 하나이고, 더 큰 정답을 계속 찾으러 가다 발견하지 못하면, 정답 + 1의 값이 출력되었다. 그래서 정답을 발견하면, 일단 tmpResult 에 넣고 다른 정답을 발견하지 못하면, tmpResult 를 출력한다.