백준 1654번 랜선 자르기

순차탐색을 이용해서 풀 수도 있지만 당연히 시간 초과가 나올것이다 이분탐색을 이용하여 시간을 단축시켜야한다 이분 탐색문제로 최대 랜선의 길이와 최소랜선의 길이(1)로 해결 가능하다

필요한 랜선의 개수와 가지고 있는 랜선의 개수를 입력 받고 가지고 있는 랜선의 길이를 입력 받는다

랜선을 K개로 나눠서 자를 때 가장 길게 만들수 있는 수를 찾는 것이다

최대 랜선의 길이는 모든 랜선의 합에서 필요한 랜선의 개수N으로 나눈값이 되고 최소는 1이된다

 

 

해결방법

먼저 중간 값을 설정 해줘야한다 입력받은 랜선의 길이를 모두 더한다 그 다음 제일 작은 값은 1로 주고 중간값을 설정한다

각각의 랜선에 대해해서 mid값으로 나눈면 몇개의 랜선이 생기는지 저장한고 그값을 마지막에 우리간 필요한 랜선의 값과 비교한뒤에 mid값을 다시 조정한다

import sys
K,N = map(int,sys.stdin.readline().split())
len_list = []

for i in range(0,K):
    len_list.append(int(sys.stdin.readline().strip()))

len_plus = sum(len_list) #랜선 길이 모두 더한것

start = 1
end = len_plus

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

    for j in len_list:
        c += j // mid
    
    if c >= N:
        start = mid + 1
        resuslt = mid
    else:
        end = mid -1

print(resuslt)