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

요구능력

이분탐색

 

문제풀이

N개의 랜선을 만들 수 있을 때, 그 중에서 최대 랜선의 길이를 구해야한다.

K개의 랜선이 주어졌다.

K개의 랜선의 길이를 적절하게 잘라서 N개의 랜선을 만듦과 동시에 최대 랜선의 길이를 구하는 문제이다.

N개의 랜선이 만들어지는지는 이분탐색을 통해서 구하자.

 

우리는 N개의 랜선을 만들기 위해 "자를 수 있는 길이"를 알아야한다.

작게는 1 단위로 자를 수 있을 것이고 크게는 가장 긴 것 만큼 자를 수 있을 것이다.

그래서 start = 1, end = 입력받은 k중에 가장큰값을 사용했다.

 

이 길이를 기준으로 이분탐색을 해보자.

중간에 있는 이 부분이 n개인지 아닌지를 구하는 부분이다.

    for i in 0..<k{
        count += (arr[i] / mid)
    }

n개보다 적다면 "자를 수 있는 길이"를 줄여서 n을 늘려야하고,

n개보다 많거나 같다면 "자를 수 있는 길이"를 늘려서 n을 줄여야한다.

이때, 중요한점은 우리는 그중에서도 최대 랜선의 길이를 구해야한다.

같은 n개를 만들더라도 랜선의 길이가 길어야한다.

그래서 upperBound의 개념을 사용해서 start가 가장 긴 길이의 초과되는 부분까지 가도록 하였다.

초과이기 때문에 출력할때 1을 빼주고 출력했다.

if count < n{
        end = mid - 1
    }else{
        start = mid + 1
    }

 

 

후기

이분탐색의 개념만 잘 안다면 응용할수있다!

 

코드

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

let maxArr = arr.max()!
var start = 1
var end = maxArr

while start <= end{
    var count = 0
    let mid = (start + end) / 2
    for i in 0..<k{
        count += (arr[i] / mid)
    }
    if count < n{
        end = mid - 1
    }else{
        start = mid + 1
    }
}
print(start - 1)