백준 13397 구간 나누기 2

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

분류: 이분탐색

---

접근방식

이분탐색으로 m개 이하의 구간으로 나눠서 만들 수 있는지 확인하면서 최소값을 갱신해나가는 방법으로 해결할 수 있었습니다.

배열의 값이 1...10000 값이기 때문에 음수는 나올 수 없으니 right를 배열의 합, left를 0으로 두고 이분탐색을 돌렸습니다.

var left = 0, right = numbers.reduce(0, +)
var minSegmentMax = right

while left <= right {
    let mid = (left + right) / 2
    if isValid(mid) {
        right = mid-1
        minSegmentMax = min(minSegmentMax, mid)
    } else {
        left = mid+1
    }
}

 

구간을 확인하는 부분은

배열의 모든 수는 구간에 포함되어야 하므로, 처음부터 최대값, 최소값을 갱신하면서

구간이 최소값을 넘어가면 카운트를 하나 늘리고 해당 수를 새로운 구간의 시작점으로 두고 다시 위 과정을 반복해나가면 됩니다.

func isValid(_ maxValue: Int) -> Bool {
    var low = numbers[0], high = numbers[0]
    var count = 1
    for num in numbers {
        if num < low {
            low = num
        }
        if num > high {
            high = num
        }
        if (high - low) > maxValue {
            count += 1
            low = num
            high = num
        }
    }
    return count <= m
}

 

해결방법

let nm = readLine()!.split(separator: " ").map { Int(String($0))! }
let (n, m) = (nm[0], nm[1])
var numbers = readLine()!.split(separator: " ").map { Int(String($0))! }

var left = 0, right = numbers.reduce(0, +)

func isValid(_ maxValue: Int) -> Bool {
    var low = numbers[0], high = numbers[0]
    var count = 1
    for num in numbers {
        if num < low {
            low = num
        }
        if num > high {
            high = num
        }
        if (high - low) > maxValue {
            count += 1
            low = num
            high = num
        }
    }
    return count <= m
}

var minSegmentMax = right
while left <= right {
    let mid = (left + right) / 2
    if isValid(mid) {
        right = mid-1
        minSegmentMax = min(minSegmentMax, mid)
    } else {
        left = mid+1
    }
}

print(minSegmentMax)

 

배운점

놀랍다.. 이분탐색이란 🤯