백준 1654 랜선 자르기

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

 

📌 해결순서

예제에서 총 11개의 랜선이 필요하므로

802 // 200 = 4

743 // 200 = 3

457 // 200 = 2

539 // 200 = 2

자르는 랜선의 길이를 200으로 설정하면 11개의 랜선이 나온다

길이가 201이라면 10개의 랜선이 나오므로 200이 문제에서 물어보는 랜선의 길이 최댓값임을 알수 있다.

 

1. 이분탐색의 시작과 끝을 정한다

-> 이 문제에서 만약 랜선이 802 + 743 + 457 + 539 만큼의 랜선이 필요하다고 하면 자르는 랜선의 길이의 최댓값은 1이다

-> 만약 랜선이 1개 필요하다고 하면 자르는 랜선의 길이의 최댓값은 802 이다

 

따라서 start : 1 / end : 802 로 놓고 탐색을 시작한다

 

2. 만들어지는 랜선의 갯수가 필요한 갯수보다 적은 경우

제일 처음 탐색하면 mid = (802 + 1) // 2 = 401 

802 // 401 = 2

743 // 401 = 1

457 // 401 = 1

539 .. 401 = 1

총 6개의 랜선이 나오므로 현재 자르는 랜선의 길이가 최대길이보다 길다

더이상 401 이상의 랜선 길이에 대해서는 탐색할 필요가 없으므로,

end = mid - 1 로 탐색 범위를 절반으로 만들어준다

3. 만들어지는 랜선의 갯수가 필요한 갯수보다 많거나 같은 경우

이 경우에는 현재 자르는 랜선의 길이가 최대길이 이거나 최대길이보다 짧음을 의미한다

따라서 현재 자르는 길이보다 더 짧은 경우에 대해서는 더이상 생각할 필요가 없으므로

start = mid + 1 로 탐색 범위를 절반으로 만들어준다.

 

📌 코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    k, n = map(int, input().split())
    lst = [int(input()) for _ in range(k)]
    ans = 0

    start = 1
    end = max(lst)

    while start <= end:
        cnt = 0
        mid = (start + end) // 2
        for line in lst:
            cnt += line // mid
        if cnt >= n:
            start = mid + 1
            ans = mid
        else:
            end = mid - 1

    print(ans)