[파이썬, 스위프트][백준 13397][💛 골드 4] (파라메트릭 서치)

🧞‍♂️ 난이도

💛 골드 4

🧞‍♂️ 문제

구간 나누기 2

https://www.acmicpc.net/problem/13397

🧞‍♂️ 유형

파라메트릭 서치

🧞‍♂️ 내 풀이

이 문제는 이분탐색의 대상을 설정하기가 조금 어려웠다. mid를 구간 점수(각 구간의 최대-최소) 의 최댓값으로 정하고, 매번 m개 이하의 구간을 만들 수 있는지 확인하면서 범위를 좁히면서 최솟값을 찾는 방식이다. 어렵다

---

🧞‍♂️ 스위프트 풀이

func isDividable(by number: Int, in numbers: [Int], M: Int) -> Bool {
    var _min = Int.max
    var _max = -Int.max
    var count = 1
    
    for i in 0..<numbers.count {
        _min = min(_min, numbers[i])
        _max = max(_max, numbers[i])
        if _max - _min > number {
            count += 1
            _max = numbers[i]
            _min = numbers[i]
        }
    }
    return count <= M
}

let NM = readLine()!.split(separator: " ").compactMap { Int($0) }
let N = NM[0]
let M = NM[1]
let numbers = readLine()!.split(separator: " ").compactMap { Int($0) }

var right = numbers.max()! - numbers.min()!
var left = 0

while left <= right {
    let mid = left + (right - left) / 2
    if isDividable(by: mid, in: numbers, M: M) {
        right = mid - 1
    } else {
        left = mid + 1
    }
}
print(left)

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기