[백준] (Swift) 1654번 - 랜선자르기 (feat. 이분탐색)

🟠 문제 링크

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

1654번: 랜선 자르기

 

🟠 나의 풀이

💡 무언가를 자르는 문제, 그리고 최대값을 구하는 문제이기 때문에 대충.. '이분탐색인가' 하는 feel이 왔다.

 

 

2번에서 정답인 200이 도출되었는데 왜 멈추지 않는가? 그 이유는, start와 end가 같아지는 지점을 찾아야, 해당 탐색을 모두 돌고나서 최대값을 찾은 것이므로, 2번에서 아무리 200이라는 결과가 도출됐어도 여기서 끝낼 방법이 없다. 200이 최대 랜선 길이라고 확신할 수 없기 때문이다!

 

이 과정을 코드로 구현하면 아래와 같다. 이분탐색도 공식? 같이 하나만 응용 해서 알고 있다면, 그리고 문제가 이분탐색임을 빨리 깨우친다면, 쉽게 풀 수 있다.

 

🟠 정답코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/1654_%EB%9E%9C%EC%84%A0%20%EC%9E%90%EB%A5%B4%EA%B8%B0/main.swift

GitHub - deslog/Algorithm: ✨ 백준, 프로그래머스 Swift 문제풀이 ✨

import Foundation

let kn = readLine()!.split(separator: " ").map { Int(String($0))! }
let k = kn[0]
let n = kn[1]
var cables = [Int]()
for _ in 0..<k {
    cables.append(Int(readLine()!)!)
}

func solution(k: Int, n: Int, cables: [Int]) -> Int {
    var start = 1
    var end = cables.max()!
    var result = 0

    while start <= end {
        let mid = (start + end) / 2
        var tempResult = 0
        for cable in cables {
            tempResult += cable/mid
        }

        // 만약 tempResult가 n보다 작으면 길이 줄여줘야함, end를 mid로
        if tempResult < n {
            end = mid - 1
        } else { // 만약 tempResult가 n보다 크면, 길이를 늘려줘야함 start를 mid로
            //그리고 결과는 n보다 크게나와도 되니까 result(랜선의 최대길이)를 갱신하면서 진행
            start = mid + 1
            result = mid
        }
    }
    return result
}

print(solution(k: k, n: n, cables: cables))