[Python] BOJ/백준 1654번 랜선 자르기

[문제]

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

1654번: 랜선 자르기

 

[풀이]

2021.08.09 - [BOJ] - [Python] BOJ/백준 2805번 나무 자르기

[Python] BOJ/백준 2805번 나무 자르기

나무와는 달리 랜선은 total += 각 랜선 길이 // mid 해야 한다는 것만 다르고 똑같은 문제

 

1. 가장 짧은 랜선의 길이를 1을 `start`로, 가장 긴 랜선의 길이인 lanlines 중 가장 큰 값을 end로 지정한다.
2. start가 end 이하일 동안 반복한다.
3. mid는 start와 end 중간이며, 갖고 있는 모든 랜선 값을 mid로 나누었을 때 총 몇 개의 랜선이 나오는지 total에 저장한다.
4. total 조건문
   1. total 값이 want 이상일 경우 start를 mid+1로 두고 다시 while문을 반복한다.
   2. total 값이 want 이하일 경우 end를 mid-1로 두고 다시 while문을 반복한다.
5. 위의 방법으로 끝까지 (start와 end가 같아지는 지점) 구했을 때 반복문을 탈출한다.
6. 결괏값인 end를 출력한다.

 

[코드]

import sys

if __name__ == '__main__':
    n, want = map(int, sys.stdin.readline().split())
    lanlines = [int(sys.stdin.readline()) for _ in range(n)]
    start, end = 1, max(lanlines)

    while start <= end:
        mid = (start + end) // 2

        total = 0
        for i in lanlines:
            total += i // mid

        if total >= want:
            start = mid + 1
        else:
            end = mid - 1
    print(end)