[swift] 백준 - 2805번: 나무 자르기

2805번: 나무 자르기

문제 푸는 데 있어 도움이 되도록 나의 풀이와 개선된 풀이를 올립니다.
또한 풀이 후 다른 사람의 풀이를 보고 참고할만한 풀이도 올립니다.
- 문제에 따라 나의 풀이만 있을 수 있습니다.
- 해당 풀이들은 풀이 중 하나일 뿐 최선의 풀이는 아닐 수 있습니다.

 

---

 

나의 풀이

let NM = readLine()!.split(separator: " ").map { Int($0)! }
let M = NM[1]
let tree = readLine()!.split(separator: " ").map { Int($0)! }
var left = 1
var right = tree.max()!
var result = 0
while left <= right {
    let mid = (left+right) / 2
    var m = 0
    for j in tree { if j > mid { m += j - mid } }
    if m >= M { left = mid + 1; result = mid }
    else { right = mid - 1 }
}
print(result)

 

- 이분탐색을 이용하여 문제를 풀 수 있습니다.

 

- 아직 조건에 따라 left값이 나와야하는지

right나 mid의 값이 나와야 하는지 헷갈리네요..ㅎ

그 부분을 좀 더 보충 공부해야겠습니다.

 

---