❓2805번 : 나무 자르기
📈 문제 요약
N개의 나무 줄지어 있을 때 적어도 M의 나무를 얻을 수 있게 자르는 최대한의 높이를 구하면 되는 문제
🤨 접근법
이분탐색 기반 결정 방법으로 최적화 문제를 해결하는 파라메트릭 서치(매개변수 탐색)의 대표적인 문제이다.
기본적으로 N개의 나무에 대해서 높이 H을 잘랐을 때 M 이상의 나무를 얻었는지 결정하는 함수는 모든 나무를 순회해야하기 때문에 O(N)(1 ≤ N ≤ 1,000,000)이다.
그리고 만약 자르는 높이를 1부터 순차탐색으로 접근한다면 O(H)(1 ≤ H ≤ 2,000,000,000)이며 무조건 시간 초과가 발생할 것이다. 정확히 어느정도 시간 복잡도에서 몇 초 이내에 문제를 해결할 수 있을지 정확하게 판단할 수는 없지만 이제 문제를 많이 풀다보니 이건 안될 것 같다는게 느껴진다.
그렇기 때문에 이분탐색 기반의 파라메트릭 서치로 접근하였다. 위에서 정리하였지만, 파라메트릭 서치를 적용할 수 있다.
- 결정 문제를 정의했을 때, 쉽게 풀 수 있는 경우
- (최소값을 구하는 경우) 최솟값이 x라면, x이상의 값에 대해서는 모두 조건을 만족
- (최대값을 구하는 경우) 최대값이 x라면, x이하의 값에 대해서는 모두 조건을 만족
높이 H를 자르기로 했을 때 잘라진 총 나무는 각 나무의 높이 대해서 H보다 큰 경우 나무 높이-H의 합으로 쉽게 구할 수 있다. 그리고 자르는 높이 H의 최대값 이하의 값에 대해서 모두 목표 M보다 많이 잘리게 되어 조건을 만족한다고 할 수 있다. 즉, 파라메트릭 서치를 적용할 수 있다.
과정은 아래에서 코드 기반으로 후술한다.
🔡 코드
import sys
input = sys.stdin.readline
def cut_tree(n):
result = 0
for tree in trees:
if tree > n:
result += tree-n
return result
def get_minimal_height(low, high):
while low <= high:
mid = (low + high) // 2
cuttedTree = cut_tree(mid)
if cuttedTree < M:
high = mid-1
else:
low = mid+1
return high
N, M = map(int, input().rstrip().split())
trees = list(map(int, input().rstrip().split()))
print(get_minimal_height(0, max(trees)))get_minimal_height() 함수는 적어도 M이상의 나무를 자를 수 있는 최대 높이를 반환하는 함수이다. 자를 수 있는 나무의 높이 범위는 0 ≤ H ≤ max(trees) 이며, 그 가운데 부터 잘라보면서 자른 길이가 M을 넘지 않는지 검사한다. (M을 넘는지 검사했으면 조금 더 자연스러웠을 것 같다.)
잘랐을 때 M을 넘지 않는다면 범위의 high를 가운데 값인 mid로 낮춰 다시 그 가운데 부터 잘라본다. 반대로 M을 넘는다면 범위의 low를 가운데 값인 mid로 높여 다시 그 가운데 부터 잘라본다. 여기까지는 이분탐색의 로직과 같다.
이제 살짝 다른 점은 조건을 만족하는 범위의 최대값을 찾는다는 점이다. 이분 탐색의 경우 특정 값을 찾는 것이기 때문에 조금은 차이가 있다.
while low <= high:
mid = (low + high) // 2
cuttedTree = cut_tree(mid)
if cuttedTree < M:
high = mid-1
else:
low = mid+1
return high이 과정에서 예제를 예시로 살펴보자
적어도 7 이상을 자르는 최고 높이를 찾으면 된다.
step 1 : low 0, high 20 → mid 10으로 자르면 k 이상 → low = mid + 1
step 2 : low 11, high 20 → mid 15로 자르면 k 이상 → low = mid + 1
여기서 이분 탐색이었다면 mid 15를 넣었을 때 정확히 7이 잘리므로 mid인 15를 반환하겠지만 이 문제는 최적화 문제이므로 조건을 만족하는 최대를 확인해야한다.
step 3 : low 16, high 20 → mid 18로 자르면 k 보다 작음 → high = mid - 1
step 4 : low 16, high 17 → mid 16으로 자르면 k 보다 작음 → high = mid -1
step 5 : low 16, high 15로 low가 high 역전. 이때 high에는 조건을 만족하는 최대 값이 담겨있다.
이번 예제에서는 정확히 7이 잘리는 경우가 최대 높이가 된다. 사소한 부분이라고 생각할 수 있지만 다른 반례에서 정확하게 k로 떨어지는 경우가 등장하지 않을 수 있기 때문에 이런 방식으로 최대 높이를 찾아야 한다. 실제로 정확히 k로 떨어지는 mid를 반환하는 방법으로 코드를 짰을 때 문제를 틀리게 된다.
📚 고찰
이분 탐색과 같은 로직의 풀이 방법이라고 무작정 코드를 짰다가 낭패를 봤었다. 이분탐색을 활용해서 결정 문제를 푸는지, 최적화 문제를 푸는지에 따라 어떤 인자를 반환할 것인지 잘 생각하고 답을 찾아야 할 것 같다.
