[BOJ] 1756번 : 피자 굽기

문제 보기

풀이

이중 for문으로 문제를 접근하기엔 300,000²으로 시간 초과가 발생할 것을 예상할 수 있다. 이분탐색으로 문제를 해결하고 싶어도 주어진 배열은 정렬된 형태가 아니므로 입력값 그대로는 이분탐색을 사용할 수 없다. 이분탐색을 사용하기 위해 주어진 배열(오븐의 지름값들)을 내림차순으로 정렬되도록 값을 변경해준다.

오븐 깊이	오븐 지름	통과할 수 있는 반죽의 최대 크기
1	5	5
2	6	5
3	4	4
4	3	3
5	6	3
6	2	2
7	3	2

위의 표와 같이 지름이 순서대로 5 6 4 3 6 2 3인 오븐을 예로 들면(오븐의 최상단이 1, 최하단이 D이므로 깊이는 인덱스에 1을 더한다), 깊이 2에서 오븐의 지름이 6이라도 바로 위인 깊이 1의 오븐의 지름이 5이므로 통과할 수 있는 피자 반죽의 지름은 5보다 클 수가 없다. 오븐의 지름은 이전 깊이의 오븐의 지름보다 작거나 같아야하므로 아래와 같은 코드로 오븐의 지름을 변경한다.

var min = oven[0]
for (i in 0 until depth) {
    min = min(min, oven[i])
    oven[i] = min
}

이제 정렬된 배열이 있으니 이분탐색을 할 수 있다. 각 피자 반죽의 위치는 찾고자 하는 피자 반죽의 지름보다 작은 값이 처음으로 나타나는 위치에서 1을 뺀 값이다. 즉, 찾고자 하는 값보다 작은 값이 처음으로 나타나는 위치를 반환하는 upperBound 구현을 응용하여 피자 반죽의 위치를 알아낼 수 있다(lowerBound는 내림차순 기준, 찾고자하는 값 이하가 처음으로 나타나는 위치).

탐색 구간의 끝점을 가장 최근 오븐에 들어간 피자 반죽의 위치로 설정하여 모든 반죽들의 위치를 탐색하면 마지막 반죽의 위치에 1을 더한 값(1-based indexing이므로)이 맨 위의 피자가 들어가 있는 깊이이다.

소스

kotlin

import java.util.Scanner
import kotlin.math.min

var d = 0
var n = 0
var st = 0
var en = 0
lateinit var a: IntArray
lateinit var b: IntArray

fun main() {
    init()
    sortOvenDiameter(a)
    println(lastIndex())
}

fun lastIndex(): Int {
    st = 0
    en = d
    for (i in 0 until n) {
        depthOfPizza(b[i])
        if (en < 0) break
        st = 0
    }

    return en + 1 // 1-based indexing : 오븐의 최상단이 1, 최하단이 D이므로
}

fun depthOfPizza(target: Int) { // 내림차순의 upperBound 사용
    while (st < en) {
        val mid = (st + en) / 2
        if (a[mid] < target) en = mid
        else st = mid + 1
    }
    en--
}

fun sortOvenDiameter(a : IntArray) {
    var min = a[0]
    for (i in 0 until d) {
        min = min(min, a[i])
        a[i] = min
    }
}

fun init() = with(Scanner(System.`in`)) {
    d = nextInt()
    n = nextInt()
    a = IntArray(d)
    b = IntArray(n)
    for (i in 0 until d) a[i] = nextInt()
    for (i in 0 until n) b[i] = nextInt()
}

정렬 순서에 따른 upperBound와 lowerBound 구현

BOJ 10816번, 숫자 카드 2 기준으로 설명

오름차순 정렬

오름차순 정렬일 경우 lowerBound는 찾고자 하는 값 이상이 처음으로 나타나는 위치인 반면에, upperBound는 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치이다.

import java.util.Scanner

var n = 0
var m = 0
lateinit var a : IntArray
lateinit var b : IntArray

fun main() {
    init()
    a.sort() // 오름차순 정렬
    b.forEach {
        print("${upperBound(it) - lowerBound(it)} ")
    }
}

fun lowerBound(target: Int): Int {
    var st = 0
    var en = a.size

    while (st < en) {
        val mid = (st + en) / 2
        if (a[mid] >= target) en = mid
        else st = mid + 1
    }
    return st
}

fun upperBound(target: Int): Int {
    var st = 0
    var en = a.size

    while (st < en) {
        val mid = (st + en) / 2
        if (a[mid] > target) en = mid
        else st = mid + 1
    }
    return st
}

fun init() = with(Scanner(System.`in`)) {
    n = nextInt()
    a = IntArray(n + 1)
    for (i in 0 until n) {
        a[i] = nextInt()
    }
    m = nextInt()
    b = IntArray(m)
    for (i in 0 until m) {
        b[i] = nextInt()
    }
}

내림차순 정렬

내림차순 정렬일 경우 lowerBound는 찾고자 하는 값 이하가 처음으로 나타나는 위치인 반면에, upperBound는 찾고자 하는 값보다 작은 값이 처음으로 나타나는 위치이다.

import java.util.Scanner

var n = 0
var m = 0
lateinit var a : IntArray
lateinit var b : IntArray

fun main() {
    init()
    a.sortDescending() // 내림차순 정렬
    b.forEach {
        print("${upperBound(it) - lowerBound(it)} ")
    }
}

fun lowerBound(target: Int): Int {
    var st = 0
    var en = a.size

    while (st < en) {
        val mid = (st + en) / 2
        if (a[mid] <= target) en = mid
        else st = mid + 1
    }
    return st
}

fun upperBound(target: Int): Int {
    var st = 0
    var en = a.size

    while (st < en) {
        val mid = (st + en) / 2
        if (a[mid] < target) en = mid
        else st = mid + 1
    }
    return st
}

fun init() = with(Scanner(System.`in`)) {
    n = nextInt()
    a = IntArray(n + 1)
    for (i in 0 until n) {
        a[i] = nextInt()
    }
    m = nextInt()
    b = IntArray(m)
    for (i in 0 until m) {
        b[i] = nextInt()
    }
}