https://www.acmicpc.net/problem/1654
1654번: 랜선 자르기
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그
www.acmicpc.net
풀이
길이가 제각각인 k개의 랜선을 일정한 크기 단위로 잘라서 n개 이상을 만들어 내려고 할 때, 그 크기 단위의 최대 값을 구하는 문제였다.
주어진 k개의 랜선으로 n개를 만들지 못하는 경우는 없다고 했으니까, 최소 1cm씩 잘라내면 항상 n개 이상을 구할 수 있다. 반대로 k = n = 1 이라면, 주어진 랜선 중 가장 긴 길이 만큼 자를 수 있다.
랜선의 길이가 21억cm을 넘기 때문에 1cm부터 차례대로 잘라보면 시간 초과가 날 것이다. 특정 크기로 잘라서 나오는 개수와 n을 비교해서 더 길게 잘라볼지, 짧게 잘라야 하는지 결정할 수 있으므로 이진 탐색을 사용할 수 있다.
시간 복잡도: O(log(2^31)) = 약 31
구현 방법
- 랜선을 입력 받는다.
- 최소 길이(m) = 1, 최대 길이(M) = 가장 긴 랜선(or 2^31 - 1)으로 시작해서, 이진 탐색으로 랜선을 잘라보며 정답을 구한다.
- 각 케이블들을 길이 (m + M) / 2로 자른 개수의 합(count)을 구한다
- if (count >= n) -> 더 길게 잘라도 n개가 넘는지 확인해본다 -> m = (m + M) / 2 + 1
- else -> 너무 길게 잘라서 모자르다 -> M = (m + M) / 2 - 1
- 위 과정을 m <= M일 때까지 반복한다.
- 이진탐색이 끝났을 때, M 값이 답이 된다.
코드 1 (구현 방법대로 m <= M일 때까지 탐색하는 방식)
import java.io.BufferedReader
import java.io.InputStreamReader
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val input = readLine().split(" ")
val k = input[0].toInt()
val n = input[1].toInt()
val cables = LongArray(k + 1) // 랜선
repeat(k) {
cables[it] = readLine().toLong()
}
print(binarySearch(cables, n))
}
fun cutCables(cables: LongArray, divisor: Long): Int {
var count = 0L
cables.forEach { cable ->
count += cable / divisor
}
return count.toInt()
}
fun binarySearch(cables: LongArray, minimumCount: Int): Long {
var answer = 0L
var lower = 1L
var upper = Integer.MAX_VALUE.toLong()
while (lower <= upper) {
val mid = (lower + upper) / 2 // 이 과정에서 Long 값이 나올 수 있다
val numberOfCut = cutCables(cables, mid)
if (numberOfCut < minimumCount) {
upper = mid - 1
} else {
lower = mid + 1
answer = mid
}
}
return answer
}
코드 2 (m < M일 때까지 탐색하는 방식)
import java.io.BufferedReader
import java.io.InputStreamReader
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val input = readLine().split(" ")
val k = input[0].toInt()
val n = input[1].toInt()
val cables = IntArray(k + 1) // 랜선
repeat(k) {
cables[it] = readLine().toInt()
}
print(binarySearch(cables, n))
}
fun cutCables(cables: IntArray, divisor: Long): Long {
var count = 0L
cables.forEach { cable ->
count += cable / divisor
}
return count
}
fun binarySearch(cables: IntArray, minimumCount: Int): Long {
var answer = 0L
var lower = 0L
var upper = Integer.MAX_VALUE.toLong()
upper += 1 // while(lower < upper) 방식에서는 최초의 upper가 답인 경우를 구할 수 없어서 1을 더해준다
while (lower < upper) {
val mid = (lower + upper) / 2
val numberOfCut = cutCables(cables, mid)
if (numberOfCut < minimumCount) {
upper = mid
} else {
lower = mid + 1
answer = mid
}
}
return answer
}'Problem Solving > 백준' 카테고리의 다른 글
| 백준 2447번: 별 찍기 - 10 (Kotlin) (0) | 2021.12.31 |
|---|---|
| 백준 1780번: 종이의 개수 (Kotlin) (0) | 2021.12.30 |
| 백준 1167번: 트리의 지름 (0) | 2021.12.25 |
| 백준 2146번: 다리 만들기 (Kotlin) (0) | 2021.12.24 |
| 백준 7576번: 토마토 (Kotlin) (0) | 2021.12.23 |
