BOJ 1654 랜선 자르기

https://www.acmicpc.net/problem/1654
시간 2초, 메모리 128MB
input :

• K N (1 <= K <= 10,000)(1 <= N <= 1,000,000)(K ≦ N)
• 랜선의 길이가 센티미터 단위의 정수로 입력된다. (1 <= 랜선의 길이 <= 2^31 - 1)

output :

• N개를 만들 수 있는 랜선의 최대 길이

조건 :

• 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정
• N개보다 많이 만드는 것도 N개를 만드는 것에 포함

---

이분탐색 문제..
low = 1
hight = max
값을 넣고 시작하자..

랜선을 구할 수 있는 경우를 볼 때, 힌트를 보면 각 랜선에서 몇 개를 구할 수 있는지 나와있는데 이를 보면 나누기를 이용 할 수 있음을 확인해야 한다.

괜히 리스트 개수 세아리려 다가 ... 미친 짓 하고 있었다.

while low <= high:
    mid = (low + high) // 2
    cnt = 0
    for item in data:
        cnt += item // mid
    if cnt >= n:
        low = mid + 1
    else:
        high = mid - 1

low에 일단 답이 되는 길이 + 1을 저장해 두었다가.
이분 탐색을 계속 실행해도 현재 low에 저장되어 있는것이 답이라면 반복문이 종료된 후에 이 숫자는 high에 저장된다.
low는 답 + 1의 숫자를 가지고 있고, 계속되는 이분 탐색을 수행하면
high = mid - 1 을 수행하기 때문에 마지막에 정답을 가지고 있는다.

import sys

k, n = map(int, sys.stdin.readline().split())
data = []

low = 1
high = -999

for i in range(k):
    num = int(sys.stdin.readline())
    data.append(num)
    high = max(high, num)

while low <= high:
    mid = (low + high) // 2
    cnt = 0
    for item in data:
        cnt += item // mid
    if cnt >= n:
        low = mid + 1
    else:
        high = mid - 1

print(high)