❓1654번 : 랜선 자르기
📈 문제 요약
K개의 랜선으로 동일한 길이의 N개의 랜선을 만들 때 최대 랜선의 길이를 구하면 되는 문제
🤨 접근법
이번 문제에 사소하지만 놓치면 안되는 문장이 있다. 바로 “N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.” 이다. 이 문장 때문에 N개의 랜선을 만들 때 최대 랜선의 길이를 구하는 문제가 적어도 N개 이상의 랜선을 만들 수 있는 최대 랜선의 길이를 구하는 최적화 문제로 바뀐다.
이부분을 놓치면 안되는게, 정확하게 N개를 만드는 경우가 주어지지 않을 수도 있다는 점이다. 그렇기 때문에 N개 이상의 랜선을 만드는 최대의 값을 적절하게 찾아야 한다.
그리고 랜선의 길이의 범위는 보다 작거나 같은 자연수이다. 단순히 선형 탐색으로 랜선의 길이를 정해서 답을 찾고자 하면 시간 제한에서 걸리게 된다.
이러한 상황에서 도입할 수 있는 방법론은 바로 매개변수 탐색이라고도 불리는 이분탐색 기반의 파라매트릭 서치이다. 이분탐색 기반의 로직이기 때문이 log 시간 내에 최적화 문제 해결이 가능하다.
자를 수 있는 최소 길이는 1, 최대 길이는 가지고 있는 k개의 랜선 중 가장 큰 길이이다. 즉, 자르는 랜선의 길이를 h라고 하면 h의 범위는 1 ≤ h ≤ max(lans)가 된다. 이 때 최소와 최대의 중간 값 mid의 길이로 랜선을 잘랐을 때 몇개를 만들어 낼 수 있는지 구한다. N개 이상의 개수를 만들 수 있다면 하한 길이를 높여 다시 중간 값으로 랜선을 만들고, N개 이상을 만들 수 없다면 상한 길이를 낮춰 다시 중간 값으로 랜선을 만드는 과정을 반복한다. 이분 탐색의 로직과 거의 유사하다.
다만, 최적화 문제이기 때문에 정확히 N개를 만들어내는 길이 h를 찾는 게 아닌, N개 이상의 랜선을 만들어낼 수 있는 h의 최대를 구해야 한다. 이 부분은 코드를 보면서 후술하겠다.
🔡 코드
import sys
input = sys.stdin.readline
def can_make_lan_of(n):
result = 0
for lan in lans:
result += lan//n
return result
def get_maximum_len(low, high):
while low <= high:
mid = (low+high)//2
if can_make_lan_of(mid) >= N:
low = mid+1
else:
high = mid-1
return high
K, N = map(int, input().rstrip().split())
lans = [int(input()) for _ in range(K)]
print(get_maximum_len(1, max(lans)))위와 같은 로직으로 구성했을 때 low가 high를 역전하는 순간에 high에는 N 이상을 만들 수 있는 가장 큰 값이 담기게 될 것이다. 왜 그런지 살펴보면
mid 길이가 N개 이상을 만들지 못할 때 mid-1이 high에 담기게 된다. 그 이후에 low가 high를 역전했다는 것은 high에 담긴 값이 N개 이상을 만드는 최대의 값이기 때문에 해당 값이 담긴 순간 그 아래의 값들은 모두 N개의 값을 만들어 냈다는 것을 의미한다.
따라서 최종적으로 함수에서는 high를 반환하여 답을 얻는다.
