[Python] 백준 풀기 1654 - 랜선 자르기

파이썬 백준 1654번

실버2

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

1654번: 랜선 자르기

 

 

 

 

문제 보기

분류: 이분 탐색, 매개 변수 탐색

 

 

 

문제 풀기

입력 받은 다양한 랜선중 가장 긴 선을 기준으로 하여 mid 값을 지속적으로 찾아 나간다.

이분할 하여 나온 mid 로 모든 랜선을 나누어 목표 개수 N 이 되도록 찾고,

N 의 개수가 충족이 되면 최대 길이를 찾기 위한 분할이 계속 일어난다.

start 와 end 가 만날때까지..

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline

def fnCutTheLan(K, N, lan_ls):
    start = 1
    end = max(lan_ls)
    
    while (start <= end):
        mid = (start + end) // 2
        count = 0
        for i in range(K):
            count += lan_ls[i] // mid
            
        if N <= count:
            start = mid + 1
        else:
            end = mid - 1
            
        print(f'count: {count}   start: {start}   end: {end}')           # test print
    
    return end


if __name__ == "__main__":
    K, N = map(int, inputdata().split())
    lan_ls = []
    for _ in range(K):
        lan_ls.append(int(inputdata().strip()))
    
    result = fnCutTheLan(K, N, lan_ls)
    print(result)



# 4 11
# 802
# 743
# 457
# 539

# count: 5   start: 1   end: 400
# count: 11   start: 201   end: 400
# count: 6   start: 201   end: 299
# count: 8   start: 201   end: 249
# count: 10   start: 201   end: 224
# count: 10   start: 201   end: 211
# count: 10   start: 201   end: 205
# count: 10   start: 201   end: 202
# count: 10   start: 201   end: 200

# 200