1654

날짜 : 2022. 12. 05 (재풀이 23.01.12)

사용 언어 : python

 

문제

 

 

코드

import sys

k, n = map(int, sys.stdin.readline().split())
lan = list()
for _ in range(k):
    lan.append(int(sys.stdin.readline()))
lan.sort()

start = 1
end = lan[-1]  # 가장 큰 길이의 랜

while start <= end:
    cnt = 0
    mid = (start + end) // 2
    #print(start, mid, end)
    for i in range(len(lan)):
        cnt += lan[i] // mid  # 잘랐을 때의 개수 구하기
    if cnt >= n:  # 개수가 n보다 크거나 같은 경우(길이를 늘려야함)
        start = mid + 1  # start 증가(최댓값 구하기 위함)
    else:  # 개수가 n보다 작은 경우 end 감소(길이를 줄여야함)
        end = mid - 1
print(end)

 

 

풀이

- start 를 1, end 를 가장 긴 랜선으로 설정한 후 binary sesarch를 진행한다.

- 개수를 구했을 때 그 개수가 n보다 크거나 같은 경우는 길이를 늘려도 가능하다는 것이기 때문에 start = mid + 1

- 개수를 구했을 때 그 개수가 n보다 작은 경우는 길이를 줄여야 한다는 것이기 때문에 end = mid - 1

- 다만 잘랐을 때의 최대 길이를 구하는 것이기 때문에 break 없이 반복문을 실행한다.

 

* m값(result)은 0이 나오면 안되기 때문에 런타임 에러를 방지하기 위해 start값을 1로 설정한다.

* 반례 (start = 0 인 경우 divided by zero 에러가 발생)

2 3

1

1

 

알게된 점

- 

 

 

참고 사이트

-