[Python] 백준 1654. 랜선 자르기

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

1654번: 랜선 자르기

문제 설명:

만약 4개의 랜선이 주어지고 11개의 랜선을 만들려고 할 때 최대 길이 갯수를 구하는 문제이다.

4개의 랜선은 예를 들면 [802, 743, 457, 539] 랜선의 길이가 주어진다.

 

최대 길이가 200일때

802cm 랜선에서 4개, 743cm 랜선에서 3개, 457cm 랜선에서 2개, 539cm 랜선에서 2개를 잘라내 모두 11개를 만들 수 있다.

 

이진탐색 

• lan에 입력받은 리스트 [802, 743, 457, 539] 가 있다고 가정한다.
• mid (이진탐색)을 하기 위해 start, end를 다음과 같이 둔다.

start, end = 1, max(lan)

 

• mid와 랜선의 갯수를 세기위해 lines 선언한다.
• 리스트를 반복하여 요소 // mid 를 하면 랜선 하나당 몇 개의 랜선이 나오는지 알 수 있다.

    mid = (start + end) // 2 
    lines = 0 #랜선 수
    for i in lan:
        lines += i // mid

 

• 랜선의 갯수가 얻으려는 랜선보다 많으면 중간값이 너무 작아서 많은 랜선을 얻게 되는 것 -> start(작은값)를 mid+1 옮겨준다.
• 랜선의 갯수가 얻으려는 랜선보다 적으면 중간값이 너무 커서 적은 랜선을 얻는 것이기 때문에 -> end(큰값)을 옮겨준다.

    if lines >= N: 
        start = mid + 1
    else:
        end = mid - 1