1654번: 랜선 자르기

문제 풀이 아이디어

전형적인 파라메트릭 서치 문제입니다. 어떤 길이로 만들 수 있는 최대 랜선의 갯수를 구하는 함수를 만들고 그 함수와 이진탐색을 활용해서 파라메트릭 서치를 구현합시다.

코드

// 입력 받기
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let K = input[0], N = input[1]
var lines = [Int]()
for _ in 0..<K {
    lines.append(Int(readLine()!)!)
}

// 길이가 size일 때 만들 수 있는 최대 랜선의 갯수
func count(size: Int) -> Int {
    var cnt = 0
    
    for line in lines {
        cnt += line / size
    }
    
    return cnt
}

// 이진탐색 초기 값
var start = 1
    //👉 최대한 많이 만들 수 있음
var end = lines.max()!
    //👉 1개 밖에 못만듬
var ans = 0

// 파라메트릭 서치 구현
while start <= end {
    let mid = (start + end) / 2
    
    if count(size: mid) >= N {
        start = mid + 1
        ans = mid
    } else {
        end = mid - 1
    }
}

print(ans)