[백준] 랜선 자르기

백준, 랜선 자르기

1654번: 랜선 자르기

TL;DR

• 이진 탐색(Binary Search)
• Parametic search

문제 요약

1. 랜선의 길이가 주어지고 해당 랜선을 잘라 만들어야 하는 랜선의 개수가 주어진다.
2. 만들어야 하는 랜선의 개수를 만족할 수 있는 경우 중 가장 긴 랜선의 길이를 반환하는 프로그램을 작성해야 한다.
3. 주어진 랜선의 개수를 초과해서 만들 수 있다.

 

- 주어진 랜선의 길이를 잘라 만든 랜선의 개수가 주어진 랜선의 개수 이상인 경우들에서 자른 랜선의 길이가 최대일 때를 출력해야 한다.

- 가장 쉽게 생각할 수 있는 방법은 최소인 1부터 주어진 랜선의 길이 중 가장 긴 랜선의 길이 사이를 조회하며 확인하는 완전 탐색(Brute force)이다. 하지만 이 경우는, 주어진 입력의 제한조건으로 인해 시간 초과이다.

- 이진 탐색을 활용한 parametic search를 사용하면 시간 내에 문제를 해결할 수 있을 것이다. 이진 탐색의 시간 복잡도는 O(logn)이다.

입출력 형태

입출력 예시

 

주어진 입력들에 대해서 랜선의 길이가 200일 때, 각 랜선 별로 4개, 3개, 2개, 2개를 만들어 11개를 만족하면서 가장 긴 랜선의 길이를 얻을 수 있다.

풀이

import sys

K, N = map(int, sys.stdin.readline().split())
lines = []
for _ in range(K):
    lines.append(int(sys.stdin.readline()))
low, high = 1, max(lines)

while low <= high:
    count = 0
    mid = (low + high) // 2
    for line in lines:
        count += line // mid
        
    if count >= N:
        low = mid + 1
    else:
        high = mid - 1

print(high)

 

문제 제약 조건에 따라 low는 1, 최대 길이는 주어진 랜선의 길이 중 가장 긴 길이로 설정한다.

이 조건 내에서 이진 탐색을 수행하는데, 우리가 알고 싶은 것은 원하는 값이 존재하는지가 아니라 원하는 조건을 만족할 때의 범위이다. 이런 문제를 parametic search를 사용해서 풀어야 한다.

while 문에서 보통의 이진 탐색 코드를 수행하는데 이 때, low는 최저 랜선의 길이, high는 최대 랜선의 길이를 의미한다.

절반으로 나누며 count가 N 이상일 경우 우리가 원하는 조건에 해당할 수 있으므로 다른 가능한 값의 조회를 위해 low를 mid + 1로 갱신한다. 그렇지 않은 경우는 범위를 좁혀야 하므로 high를 mid - 1로 갱신한다.

while문이 수행되고 나면 high에는 조건을 만족하는 범위에 최대값이 저장되게 된다. 이는 우리가 문제에서 원하는 조건이므로 high를 출력하면 답을 얻을 수 있다. low에는 조건을 만족하는 범위의 최소값이 저장되어야 하지만, 현재 작성한 코드에서는 반복문의 범위가 low가 high보다 클 경우이므로 이에 해당하지 않는다. 최소값을 구하기 위해서는 이진 탐색 코드 내에 또 다른 조건문을 추가해주면 될 것이다.