백준 1654번 랜선 자르기 - SWIFT

문제

---

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

 

문제 링크

1654번: 랜선 자르기

 

 

풀이

---

가장 쉬운 방법은 모든 경우의 수를 하나씩 해보는 것이다.

하지만 다들 알다시피 이렇게 하면 시간 복잡도가 O(N^2)이 되어 시간초과가 나온다.

그래서 이분 탐색을 이용해서 확인해볼 것이다.

전부 다 검사하지 않아도 정답에 근접한 범위만 계속 확인하게 되므로 O(logN)이면 해결이 된다.

 

 

프로그램 동작

---

핵심적인 동작에 들어가기 전에, 이분 탐색은 정렬된 배열에서만 사용이 가능하므로 값을 받고 정렬을 해준다.

코드를 보면 값을 받는 중간 중간 최대값을 갱신해줬는데, 어차피 정렬하면 맨 뒤가 최대값이 되는걸 왜 했는지는 모르겠다...

 

 

1. 가장 먼저 왼쪽 맨 끝을 0, 오른쪽 맨 끝을 배열의 최대값으로 한다.

그리고 그 둘을 평균내어 중간값을 구한다.▼

 

 

2. 이 중간값을 가지고 랜선의 개수를 구해본다.

이렇게 만든 랜선의 개수는 5개로 원하는 랜선 수인 11보다 부족하다.▼

 

 

3. 2번의 결과는 랜선의 길이를 401이상으로 하면 랜선 수가 무조건 부족해진다는 뜻이므로, 이제부터는 0부터 400의 범위만 보면 된다.

왼쪽은 그대로 0, 오른쪽은 중간값 - 1로 재설정 해준다.

그리고 아까와 마찬가지로 재설정한 왼쪽과 오른쪽 값으로 중간값을 다시 구한다.▼

 

 

4. 이제 새로 구한 중간값으로 랜선 개수를 다시 구해본다.

구하려는 랜선 길이와 같고, 정답 값보다 크므로 갱신해준다.▼

 

 

5. 정답값이 나왔지만, 이게 최대값이라는 보장은 없다.

하지만 최대값을 구할거면 방금 사용했던 중간값보다는 큰 값을 대입해서 확인해봐야하므로, 0부터 200까지의 범위는 필요 없어졌다.

왼쪽을 중간값 + 1, 오른쪽은 그대로 400으로 재설정 해준다.

그리고 아까와 마찬가지로 재설정한 왼쪽과 오른쪽 값으로 중간값을 다시 구한다.▼

 

 

6. 방금 구한 중간값으로 랜선 개수를 다시 구해본다.

랜선 개수가 부족하다.▼

 

 

7.이제부터는 아까 했던 과정을 계속 반복해준다.

랜선 길이가 부족하면 왼쪽값은 그대로, 오른쪽 값을 중간값 - 1로 갱신,

랜선 길이가 딱 맞거나 많으면 왼쪽값을 중간값 + 1, 오른쪽 값은 그대로로 갱신한다.

이런 식으로 범위를 계속 줄여나가면서 값을 갱신해본다.

201까지 검사를 해봄에도 불구하고, 값은 갱신되지 않으므로, 정답은 200이 된다.▼

 

 

Swift 코드

---

import Foundation

// 라이노님의 FileIO
final class FileIO {
    private var buffer:[UInt8]
    private var index: Int

    init(fileHandle: FileHandle = FileHandle.standardInput) {
        buffer = Array(fileHandle.readDataToEndOfFile())+[UInt8(0)]
        index = 0
    }

    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }

        return buffer.withUnsafeBufferPointer { $0[index] }
    }

    @inline(__always) func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true

        while now == 10
                || now == 32 { now = read() }
        if now == 45{ isPositive.toggle(); now = read() }
        while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }

        return sum * (isPositive ? 1:-1)
    }

    @inline(__always) func readString() -> String {
        var str = ""
        var now = read()

        while now == 10
                || now == 32 { now = read() }

        while now != 10
                && now != 32 && now != 0 {
            str += String(bytes: [now], encoding: .ascii)!
            now = read()
        }

        return str
    }
}

var file = FileIO()
let K = file.readInt()
let N = file.readInt()
var LAN = Array(repeating: 0, count: K)
var MAX = 0
var left = 1
var right = 0
var answer = 0

for i in 0..<K {
    LAN[i] = file.readInt()
    MAX = max(MAX, LAN[i])
}

LAN.sort()
right = MAX

while left <= right {
    var count = 0
    let mid = (left + right) / 2

    for i in 0..<K {
        count += LAN[i] / mid
    }
    if count >= N {
        if answer < mid {
            answer = mid
        }
        left = mid + 1
    } else {
        right = mid - 1
    }
}

print(answer)