[백준 1654] 랜선 자르기

문제

K개의 랜선이 있을 때 각각 같은 길이로 잘라서 N개의 랜선을 만든다. 자르고 남은 길이는 사용할 수 없고 N개보다 많이 만들어도 된다.

이때 최대 어느 길이로 잘라야 N개를 만들 수 있는지 구하라.

 

입력

첫째 줄에 K, N을 입력한다. (K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수)

이어서 K 줄에 걸쳐서 랜선의 길이가 주어진다. 랜선의 길이는 2^31-1보다 이하이다.

 

출력

N개를 만들 수 있는 랜선의 최대 길이를 출력한다.

---

접근

이 문제를 통해 이분탐색이 무엇인지 알았다.

이분탐색은 어떠한 범위의 값에서 특정한 값을 찾을 때 범위를 두 개로 나눠서 찾아보는 것이다.

가장 작은 값과 가장 큰 값을 더한 중간값을 찾고 중간값을 기준으로 찾아야하는 수와 비교했을 때 작다면 왼쪽의 범위를 좁히고 크다면 오른쪽의 범위를 좁힌다.

 

구현

원래 이분탐색은 정렬이 되어있는 수열에서 사용할 수 있지만 여기서는 중간값을 찾아서 랜선들을 모두 나눠보는데 사용되기 때문에 정렬이 될 필요가 없으며

처음에 왼쪽과 오른쪽의 값을 1과 랜선의 최대 길이로 넣어준다.

이제 left와 right를 통해 중간값을 통해 중간값으로 랜선의 길이를 모두 나눠본다.

 

이때 만들어야하는 N보다 작다면 right를 mid-1로 만들고 이상이라면 left를 mid+1로 만든다.

left가 right 이상이되면 탐색이 종료되며 최종적으로 right가 구하고자 하는 해가 된다.

import sys
input = sys.stdin.readline

K, N = map(int, input().split())
numbers = [int(input()) for _ in range(K)]

left = 1
right = max(numbers)

while left <= right:
    mid = (left+right)//2
    print(mid)
    count = 0
    for number in numbers:
        count += number//mid

    if count >= N:
        left = mid + 1
    else:
        right = mid - 1
print(right)