플랫폼 | 번호 | 제목 | 유형 | 난이도 | 언어 |
---|---|---|---|---|---|
백준 | 2805 | 나무 자르기 | 이분탐색 | 실버2 | Swift, Python |
문제를 처음 다 읽었을 때 이분 탐색으로 접근해야겠다는 생각이든 이유는 다음과 같다.
- 우리가 구해야 하는 절단기의 높이는 찾을 수 있는 규칙이 없고 직접 임의의 값을 검증을 해보면서 찾아야한다.
- Brute Force로 절단기의 높이를 찾기에는 입력값이 매우 크다.
이분 탐색으로 접근 방법을 선택했으면 먼저 탐색할 데이터의 범위를 결정해 줘야 한다.
결국에 찾아야 하는 값이 절단기의 높이의 최댓값
이므로 범위를 0 ~ 가장 높은 나무의 높이
로 정했다. 상근이가 가져가야 하는 나무의 길이(M)는 1 이상이기 때문에 굳이 절단기의 높이를 가장 높은 나무의 높이
보다 높게 설정하여 탐색 범위를 늘릴 필요가 없다. (어차피 가장 높은 나무의 높이 보다 높게 설정하면 절단된 나무 높이의 합은 모두 0이다)
이분 탐색의 범위를 정했으니 중간값(mid)을 통해 빠르게 탐색하면 된다.
탐색 과정에서 중간값(mid, 임의의 절단기 높이)를 검증해야 한다. 주어진 나무들을 중간값(임의의 절단기 높이)으로 자르고 잘려진 나무들의 높이 합을 M(상근이가 가져가려고 하는 나무의 길이)과 비교 하면서 이분 탐색하면 된다.
잘린 나무들의 높이의 합이 M 보다 작다는 것은 가져가려고 하는 나무의 길이가 부족하다는 것이다. 그렇기 때문에 절단기의 높이를 낮춰 나무를 더 길게 잘라야 한다. 그래서 totalH(swift) or length(python)
가 M 보다 작으면 end = mid - 1
이 된다.
let input = readLine()!.split(separator: " ").map{ Int($0)! }
let (N, M) = (input[0], input[1])
var tree = readLine()!.split(separator: " ").map{ Int($0)! }
var start = 0
var end = tree.max()!
while start <= end {
let mid = (start + end) / 2
var totalH = 0
for t in tree {
let h = t - mid
if h > 0 { totalH += h }
}
if totalH < M {
end = mid - 1
} else {
start = mid + 1
}
}
print(end)
N, M = map(int, input().split())
heighs = list(map(int, input().split()))
start = 1
end = max(heighs)
while start <= end:
mid = (start + end) // 2
length = 0
for heigh in heighs:
if heigh > mid:
length += heigh - mid
if length >= M:
start = mid + 1
else:
end = mid - 1
print(end)
지금까지 99클럽 코테 스터디를 하면서 기본적인 이분 탐색 문제를 풀어오고 있는데 이번 문제도 딱 기본 문제였던 것 같다. 이분 탐색 기본 문제에는 어느 정도 익숙해져서 인지 어렵지 않게 풀어낼 수 있었다.
이 문제의 가장 핵심은 접근 방식을 찾고(이분 탐색 등), 만약 이분 탐색이라면 탐색 범위 결정과 탐색 데이터 검증 조건이다.