랜선자르기 (결정알고리즘, 이분탐색)

인프런 김태원님의 파이썬 알고리즘 문제풀이를 듣고 작성한 글입니다.

https://inf.run/Uiep

파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의

#내 풀이
k, n = map(int, input().split())
a = []
for i in range(k):
    a.append(int(input()))

start = max(a)//2

while True:
    cnt = 0
    for x in a:
        cnt += x//start
    if cnt == n:
        break
    elif cnt > n:
        start += 1
    else:
        start -= 1

print(start)

 

내 방식대로 문제를 풀어봤는데 채점 프로그램에서 시간초과가 발생했다.

그 이유는 start += 1, 또는 start -= 1을 하는 것이 아니라

이분 탐색으로 그 길이를 찾아야하는데 방법을 잘 모르겠어서 강의를 봤다.

 

#강의 풀이

def Count(len):
    cnt = 0
    for x in Line:
        cnt += (x//len)
    return cnt

k, n = map(int, input().split())
Line = []
res = 0
largest = 0
for i in range(k):
    tmp = (int(input()))
    Line.append(tmp)
    largest = max(largest, tmp)

lt = 1
rt = largest
while lt <= rt:
    mid = (lt+rt)//2
    if Count(mid) >= n:
        res = mid
        lt = mid + 1
    else:
        rt = mid - 1
print(res)

 

lt = 1, rt는 최대길이, mid는 중간지점을 해놓고

if Count(mid) >= n:

     res = mid

     lt = mid + 1

 

res에 mid를 저장하여 mid의 최댓값을 구하는 부분이 잘 생각이 안났었다.