[백준] 1654 랜선 자르기

문제 설명

문제 링크

길이가 모두 다른 랜선들이 K개 주어졌을 때, 이를 잘라 N개 이상의 같은 길이의 랜선을 만들어야 한다. 이 때, 잘린 랜선의 길이는 가능한 길게 해야한다.

이 문제는 정글 당시에 주어진 문제 중 하나였는데, 그 당시에는 부족한 실력으로 인해 풀지 못하였기에 다시 풀어보기로 했다.

문제 풀이

다시 한 번 이분 탐색 문제이다. 다행히 이제 어느정도 이해가 되는 듯 하다. 이분 탐색 문제를 해결하기 위해서는 우선 적절한 초기 탐색범위 Left와 Right를 설정해주어야 한다. 해당 문제에는 ‘N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다` 라고 명시되어 있었기 때문에 최소 길이를 1로 잡았으며, 최대 길이는 주어진 랜선 길이 중 최대값으로 설정하였다. 조금만 더 시간을 들여 생각해봤으면 더욱 범위를 좁힐 수 있을 것 같긴 하지만, 빨리 푸는 것 또한 중요하다고 생각했고, 시간 제한 또한 넉넉한 편이었기에 여기서 범위를 살짝 줄인다고 크게 영향갈 것 같지는 않았다.

이렇게 초기 Left와 Right 끝값들을 설정해준 후에는 이를 사용해 mid값, 즉 랜선의 길이를 설정하면 된다.

만약 이렇게 자른 랜선의 개수가 N값보다 적으면 너무 길게 잘랐다는 뜻이니 Right를 낮추어야 하며, 랜선의 개수가 N값과 같거나 크면 우선 이를 저장한 후 ‘최대값’을 얻기 위해 Left를 올려 다시 한 번 탐색한다.

탐색을 마친 후 얻은 값을 출력해주면 된다.

코드

import sys
input = sys.stdin.readline

def binary_search(arr, key):
    lt = 1
    rt = max(arr)

    longest = 1

    while lt <= rt:
        mid = (lt + rt)//2
        amnt = 0
        
        for elem in arr:
            amnt += elem//mid

        if amnt >= key:
            longest = max(longest, mid)
            lt = mid + 1
        else:
            rt = mid - 1

    return longest

if __name__ == "__main__":
    K, N = map(int, input().split())
    
    lan = list()
    for _ in range(K):
        lan.append(int(input()))

    ans = binary_search(lan, N)

    print(ans)