문제 출처 : https://www.acmicpc.net/problem/1654

---

문제 파악

• K : 이미 가지고 있는 랜선의 개수
• N : 필요한 랜선의 개수
• K_list : 각 랜선의 길이

K_list 에 있는 랜선을 적절히 잘라 N개 이상의 랜선을 만들어야 한다.
이때 만들 수 있는 랜선의 최대 길이 L을 구하는 문제다.

문제 설명이 직관적이지 않아 예제를 기준으로 파악해보면,

랜선: [802, 743, 457, 539]
필요: 11개

이 네 개의 길이를 모두 더하면 2541.
평균적으로 나누면 2541 / 11 = 231 이다.

하지만 231cm로는 모든 랜선을 쪼갤 수 없다.
예를 들어 457cm 랜선은 231로 자르면 1개밖에 못 만든다(231 * 2 = 462 > 457).

즉,
“길이 L로 자르면 몇 개가 나오는가?”
이걸 판단해가며 가능한 가장 큰 L을 찾아야 한다.

이때 N이 최대 1,000,000이라 완전탐색(1씩 줄여가며 확인)은 시간적으로 불가능하다.

---

처음 해답 및 풀이

총합을 N으로 나눈 값을 최대 랜선 길이 후보(cand)로 잡고,
cand를 1씩 줄여가며 cur == N 이 되는 시점을 찾는 방식이었다.

import sys
input = sys.stdin.readline

K, N = map(int,input().split())

K_list = []
for _ in range(K):
    K_list.append(int(input()))

cand = sum(K_list) // N # 최대 랜선 길이 후보 , 231

cur = 0 # 현재 랜선의 수

# 현재 랜선의 수가 N이 될때까지 계속 반복, cand를 -1씩 계속함
while cur != N:    

    for k in K_list:
        cur += (k // cand)

    
    if cur == N:
        print(cand)
        break


    cand -= 1 # cand 하나씩 줄이기
    cur = 0 # 초기화

문제는 cand가 최대 수억 단위까지 갈 수 있기 때문에
매 반복에서 K_list를 순회하면 시간복잡도가 터진다.

답은 우연히 맞을 수 있어도 시간초과는 피할 수 없었다.

---

해답 및 풀이

랜선 길이가 커질수록 만들 수 있는 랜선 수는 감소하는 단조적인 관계가 있다.
따라서 이분탐색을 적용할 수 있다.

• left = 1 (최소 길이 후보)
• right = max(K_list) (최대 길이 후보)

mid 길이로 잘랐을 때 cur >= N이면 mid는 가능하다는 의미 → 더 큰 길이를 탐색
반대로 cur < N이면 mid가 너무 길다는 의미 → 길이를 줄여야 함

import sys
input = sys.stdin.readline

K, N = map(int,input().split())

K_list = []
for _ in range(K):
    K_list.append(int(input()))

left = 1 # 최소 랜선 길이 후보
right = max(K_list) # 최대 랜선 길이 후보
answer = 0

while left <= right:
    mid = (left+right)//2

    cur = 0
    
    for x in K_list:
        cur += x // mid
    
    if cur >= N:
        # mid 길이로 충분히 잘라짐 → 더 길게 잘라도 되나 보자
        answer = mid
        left = mid + 1

    else:
    # mid 길이가 너무 길어서 개수가 부족함 → 길이를 줄이자
        right = mid - 1
print(answer)