여러개의 랜선을 잘라 다시 길이가 같은 N개의 랜선으로 만들 때,
만들 수 있는 최대 길이를 구하는 문제입니다.
이분탐색 문제로, 만들 수 있는 모든 길이를 구하는 방법이 아닌,
범위를 절반씩 잘라서 빠른 시간 내에 구할 수 있도록 합니다.
mid
길이로 잘랐을 때, 이미 N개의 랜선을 만들 수 있다면,
mid
보다 짧은 길이는 확인할 필요가 없습니다.
반대로 mid
길이로 잘랐을 때, N개의 랜선을 만들 수 없다면,
mid
보다 긴 길이는 확인할 필요가 없습니다.
이렇게 범위를 크게 줄여 나가서 빠르게 탐색할 수 있도록 합니다.
import sys
def main():
K, N = map(int, input().split())
length = [int(sys.stdin.readline().rstrip()) for _ in range(K)]
start = 1
end = max(length)
while start <= end:
mid = (start + end) // 2
count = 0
for idx in range(K):
count += length[idx] // mid
if count < N:
end = mid - 1
else:
start = mid + 1
print(end)
if __name__ == "__main__":
main()
이분탐색 알고리즘에 대해 학습하였습니다.
조건만 잘 설정한다면, 정렬도 필요없고, 모든 element들을 탐색할 필요도 없습니다.
이때, 종료 조건이나 마지막 결과값에 신경을 써서 오류가 나지 않도록 해야합니다.