김경록의 앱 개발 여정

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

Algorithm

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

Kim Roks 2025. 1. 16. 17:17

풀이 아이디어

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

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

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

 

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

 

풀이

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)

'Algorithm' 카테고리의 다른 글

[Swift 백준] 14465 소가 길을 건너간 이유 5  (0) 2025.01.21
[Swift 백준] 18870 좌표 압축  (0) 2025.01.20
[Swift 백준] 2512 예산  (0) 2025.01.15
[Swift 백준] 나무 자르기  (0) 2025.01.14
[Swift 백준] 1965 상자넣기  (0) 2025.01.13