[Swift 백준] 17266 어두운 굴다리

풀이 아이디어

이분탐색 + 구현 문제입니다.

이분탐색만으로 어떻게 해결해야하는지 애를 먹었는데

조명으로 커버가 되는지 확인하는 작업을 거치는게 오히려 포인트인 문제였습니다.

 

자세한 설명은 주석 참고해주세요

 

풀이

import Foundation

let n = Int(readLine()!)!
let m = Int(readLine()!)!
let input = readLine()!.split(separator: " ").map { Int($0)! }

func isCoverd(with height: Int) -> Bool {
    var lastCovered = 0
    for i in input {
        if i - height > lastCovered {
            return false
        }
        lastCovered = i + height
    }
    return lastCovered >= n
}

var left = 0
var right = n
var answer = n

while left <= right {
    let mid = (left + right) / 2
    // 커버가 되면 이미 충분한거니 줄여봅니다
    if isCoverd(with: mid) {
        answer = mid
        right = mid - 1
	// 커버가 안된다면 늘려봅니다
    } else {
        left = mid + 1
    }
}

print(answer)