[파이썬] 백준 1654번 랜선 자르기

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

1654번: 랜선 자르기

 

[문제 이해]

이미 가지고 있는 랜선 K개를 가지고 잘라서 N개의 랜선을 만드려고 할 때 랜선 하나의 길이가 최대가 되는 수를 구하는 문제이다.

 

[문제 풀이]

큰 범위를 탐색 범위로 가질 때 이진 탐색을 활용하면 되는데 이 문제도 탐색 범위가 넓어 이진 탐색을 구현하여 적용하면 되겠다고 생각했다. 강의를 들으면서 풀었던 떡볶이 떡 만드는 문제와 동일한 방식으로 풀이를 하면 됐었는데 약간의 다른 점도 물론 존재한다. mid의 값은 start와 end의 값을 나눈 몫으로 지정하게 되고, 이 mid를 기준으로 랜선을 자른다고 했을 때 몇 개의 랜선이 나올 수 있는지는 몫을 통해서 구할 수 있다. 따라서 기존에 입력 받은 랜선의 길이에 해당하는 리스트의 각 원소에서 mid의 값을 나눴을 때의 몫을 새로운 리스트에 저장해준다. 이후 새롭게 만들어진 리스트가 각 원소에 따라서 생성되는 랜선의 개수이므로 새롭게 만들어진 리스트의 모든 원소의 합을 구했을 때 목표한 랜선 개수를 넘으면 답을 구할 수 있다. 이때 만들기로 한 랜선의 개수는 목표한 개수보다 많아져도 상관 없기 때문에 새롭게 만든 리스트의 원소 합을 구했을 때, 목표한 값보다 많은 경우에는 일단 mid를 result라는 변수에 저장해두고 최적의 값을 구하기 위해 start의 값을 mid 보다 하나 클 때로 변경하면 된다. 

end 가 작아질 수록 mid의 값이 작아지기 떄문에 생기는 랜선의 개수는 많아지고 반대로 start가 커질 수록 mid의 값이 커지므로 랜선의 개수가 적어진다.

import sys

k, n = map(int, sys.stdin.readline().split())
array = list()

for i in range(k):
    array.append(int(sys.stdin.readline().strip()))

start = 1
end = max(array)
result = 0

while start <= end:
    mid = (start + end) // 2 # mid는 최대 길이가 될 값

    # mid에 해당하는 값으로 리스트의 모든 원소에서 나올 수 있는 랜선의 개수를 구해서 새로운 배열에 저장
    new_array = list(map(lambda x: x // mid, array))

    # 만들어진 리스트의 모든 원소에 대한 합 => n과 비교를 통해 조건을 충족하는지 확인
    total = sum(new_array)

    if total < n: # 랜선의 총 개수가 n보다 작으면 
        end = mid - 1 # mid가 더 작아져야 더 많이 잘릴 수 있음
    else:
        result = mid # n개보다 많이 만들어도 n개를 만드는 것에 포함되므로 저장
        start = mid + 1 # 최적의 값을 찾을 떄까지 반복하므로 start 값을 현재 mid보다 큰 값으로 수정

print(result)