백준 문제풀이 - 1654 번

링크 -> https://www.acmicpc.net/problem/1654

1. 요약 및 풀이방법

여러개의 랜선을 잘라 다시 길이가 같은 N개의 랜선으로 만들 때,
만들 수 있는 최대 길이를 구하는 문제입니다.

이분탐색 문제로, 만들 수 있는 모든 길이를 구하는 방법이 아닌,
범위를 절반씩 잘라서 빠른 시간 내에 구할 수 있도록 합니다.

mid길이로 잘랐을 때, 이미 N개의 랜선을 만들 수 있다면,
mid보다 짧은 길이는 확인할 필요가 없습니다.

반대로 mid 길이로 잘랐을 때, N개의 랜선을 만들 수 없다면,
mid보다 긴 길이는 확인할 필요가 없습니다.

이렇게 범위를 크게 줄여 나가서 빠르게 탐색할 수 있도록 합니다.

2. Code

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()

3. 학습 내용

이분탐색 알고리즘에 대해 학습하였습니다.
조건만 잘 설정한다면, 정렬도 필요없고, 모든 element들을 탐색할 필요도 없습니다.
이때, 종료 조건이나 마지막 결과값에 신경을 써서 오류가 나지 않도록 해야합니다.

4. 결과