백준_1654번

1654번 랜선자르기

가지고 있는 랜선 개수와 필요한 랜선 개수가 주어지고
가지고 있는 랜선의 길이가 차례로 주어진다.

같은 길이로 잘랐을 때 필요한 랜선 개수를 충족하는 길이 중
가장 긴 길이를 출력하는 문제.

# 시간초과
 import sys
 input = sys.stdin.readline

 n,m = map(int,input().split())
 lst = [int(input()) for _ in range(n)]
 cnt = sum(lst) // m 
# 랜선을 모두 합하였을 때 m개의 개수를 만들 수 있는 가장 긴 길이(cnt)
# 랜선은 모두 길이가 다르고 붙힐 수 없기 때문에 
# 각 랜선을 cnt로 나눴을 때 m개의 랜선이 나오는지 확인해야 했다.
 while 1:
     line = 0 # 랜선 개수 카운팅
     for x in lst:
         line += (x // cnt) 
         # 각 랜선을 cnt로 나눴을 때 나오는 랜선 개수를 더해준다.
     if line == m: # 만약 랜선 개수가 필요한 랜선 개수와 같아면
         print(cnt) # 해당 길이 출력하고 탈출
         break
     else: # 아니라면 길이를 1 줄이고 다시 확인
         cnt -= 1

가지고 있는 랜선 개수, 필요 개수, 각 랜선 길이의 입력 값의 최대 수가
매우 크기 때문에 해당 방법으로는 시간초과가 나왔다.
완전 탐색이 불가하므로 이분탐색을 해야 했다.

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
lst = [int(input()) for _ in range(n)]
x,y = 1,max(lst)

while x <= y:
    mid = (x+y) // 2 # 가지고 있는 랜선 중 가장 긴 랜선의 중앙 값으로 확인한다.
    line = 0
    for i in lst:
        line += (i//mid) # 중앙 값으로 각 랜선을 나눴을 때
    if line < m: # 총 라인 개수가 필요한 개수보다 작으면
        y = mid - 1 # x 부터 중앙값보다 1 작은 수까지의 중앙값으로 다시 확인.
    else: # 필요 개수보다 많거나 같으면
        x = mid + 1 # 중앙값에서 1 큰 수 부터 y 까지의 중앙값으로 다시 확인. 
print(y)