백준 | 1654

자르기만 가능한 랜선 K개의 길이가 주어진다.
똑같은 길이로 N개의 랜선을 만들 때, 이 랜선의 최대 길이(정수)를 구하는 문제이다.

랜선 길이가 될 수 있는 값은 1부터 max(lan)이다.
max()가 상한 값인 이유는 자를 수 있는 랜선의 최대 길이를 구하는 문제이기 때문이다.

이제 범위에 포함되는 값을 하나씩 확인하며 최댓값을 구해야 하는데,
반복문으로 1씩 늘려가는 것보단 이진 탐색을 통해 탐색 범위를 반으로 좁혀가는 방법을 택했다.

탐색 과정에서 주의해야 할 점은 범위 설정(등호를 포함할 것인가?)이다.

아래 코드를 기준으로 다음과 같은 부분이 주의해야 할 부분이다.

1. while low <= high
   '<' 대신 '<='를 쓰면 오답이 나온다.
   이유는 low, high 값이 같은 경우도 최대 길이가 나올 수 있기 때문이다.
   모든 경우에 대한 탐색을 보장하기 위해 등호를 포함시키는 것이 맞고,
   만약 문제가 있다면 while문 안의 조건에서 처리가 될 것이다.

2. if cnt >= n
   cnt가 n과 같다고 탐색이 끝나는 것이 아니라,
   1이라도 더 큰 값 역시 해당 조건을 만족하면서 정답이 될 수 있다.
   그래서 '>' 대신 '>='를 써야 한다.

코드(정답)는 다음과 같다.

# 1654

import sys

k, n = map(int, sys.stdin.readline().split())
lan = [int(sys.stdin.readline()) for _ in range(k)]

# ans: 구하고자 하는 값(랜선 최대 길이)
ans = 0

# 이진 탐색
low, high = 1, max(lan)
while low <= high:
    # mid: 자르려는 랜선 길이
    mid = (low + high) // 2

    # cnt: mid로 잘라서 만들 수 있는 랜선 개수
    cnt = 0
    for l in lan:
        cnt += (l // mid)
    
    # 랜선 최대 길이 찾기
    # 1) 더 길게 잘라도 되는 경우
    if cnt >= n:
        ans = mid
        low = mid + 1
    # 2) 더 짧게 잘라야 하는 경우
    else:
        high = mid - 1

print(ans)