99클럽 코테 스터디 4기 6일차 TIL - 백준: 나무 자르기(2805) Swift & Python

레일리·2024년 11월 2일

99클럽 코테 스터디 4기

목록 보기

6/26

ℹ️ 문제 정보

플랫폼	번호	제목	유형	난이도	언어
백준	2805	나무 자르기	이분탐색	실버2	Swift, Python

🚀 나의 접근 방법

문제를 처음 다 읽었을 때 이분 탐색으로 접근해야겠다는 생각이든 이유는 다음과 같다.

우리가 구해야 하는 절단기의 높이는 찾을 수 있는 규칙이 없고 직접 임의의 값을 검증을 해보면서 찾아야한다.

Brute Force로 절단기의 높이를 찾기에는 입력값이 매우 크다.

이분 탐색으로 접근 방법을 선택했으면 먼저 탐색할 데이터의 범위를 결정해 줘야 한다.

결국에 찾아야 하는 값이 절단기의 높이의 최댓값이므로 범위를 0 ~ 가장 높은 나무의 높이 로 정했다. 상근이가 가져가야 하는 나무의 길이(M)는 1 이상이기 때문에 굳이 절단기의 높이를 가장 높은 나무의 높이 보다 높게 설정하여 탐색 범위를 늘릴 필요가 없다. (어차피 가장 높은 나무의 높이 보다 높게 설정하면 절단된 나무 높이의 합은 모두 0이다)

이분 탐색의 범위를 정했으니 중간값(mid)을 통해 빠르게 탐색하면 된다.

탐색 과정에서 중간값(mid, 임의의 절단기 높이)를 검증해야 한다. 주어진 나무들을 중간값(임의의 절단기 높이)으로 자르고 잘려진 나무들의 높이 합을 M(상근이가 가져가려고 하는 나무의 길이)과 비교 하면서 이분 탐색하면 된다.

잘린 나무들의 높이의 합이 M 보다 작다는 것은 가져가려고 하는 나무의 길이가 부족하다는 것이다. 그렇기 때문에 절단기의 높이를 낮춰 나무를 더 길게 잘라야 한다. 그래서 totalH(swift) or length(python)가 M 보다 작으면 end = mid - 1이 된다.

✍️ 나의 코드

Swift

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)

Python

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)