백준 1756번: 피자 굽기

문제: https://www.acmicpc.net/problem/1756

문제 풀이

구현, 그리디

oven[i] = 오븐의 깊이 i까지 통과할 수 있는 피자 반죽의 지름

pos = 피자 반죽이 들어갈 수 있는 가장 깊은 빈 칸

pizza = 현재 오븐에 들어가야 하는 피자 반죽의 지름

oven 배열을 D + 1 크기로 정의하고 Int.MAX_VALUE로 초기화함

배열의 인덱스 i를 1부터 D까지 반복하며 현재 칸의 오븐의 지름을 입력받고 전 칸까지 통과할 수 있는 피자 반죽의 지름 oven[i - 1]과 비교하며 더 작은 값을 oven[i]에 저장해 현재 깊이까지 통과할 수 있는 피자 반죽의 지름을 구함

피자 반죽을 하나하나 놓아야 하므로 현재 오븐에 피자 반죽이 들어가 있지 않으므로 pos에 오븐의 최대 깊이 D를 저장함

피자 반죽의 지름을 pizza에 입력받고 이 값과 oven[pos]를 비교해 pizza보다 크거나 같아질때까지 pos를 1씩 감소시켜 현재 피자 반죽이 들어갈 수 있는 최대 깊이의 칸 pos를 찾음

만약 이 과정에서 pos가 1보다 작아지게 된다면 피자 반죽이 들어갈 수 있는 칸이 없는 것이므로 pos에 -1을 대입하고 반복문을 탈출함

그게 아니라면 피자 반죽이 들어갈 수 있는 칸을 찾은 것이므로 현재 칸에 피자 반죽을 놓았다는 것을 나타내기 위해 pos를 1 감소시킴

이렇게 반복문을 거치면 pos에 마지막 피자 반죽이 들어간 윗 칸의 깊이 또는 모든 피자 반죽이 들어가지 못했다는 뜻의 -1이 저장되므로 pos + 1을 출력하면 정답

풀이 설명

월드피자 원주 지점에서 N개의 피자 반죽을 오븐에 넣고 구우려고 한다. 그런데, 월드피자에서 만드는 피자 반죽은 지름이 제각각이다. 그런가하면, 월드피자에서 사용하는 오븐의 모양도 몹시 오묘하다. 이 오븐은 깊은 관처럼 생겼는데, 관의 지름이 깊이에 따라 들쭉날쭉하게 변한다. 아래는 오븐의 단면 예시이다.

피자 반죽은 완성되는 순서대로 오븐에 들어간다. 이렇게 N개의 피자가 오븐에 모두 들어가고 나면, 맨 위의 피자가 얼마나 깊이 들어가 있는지가 궁금하다. 이를 알아내는 프로그램을 작성하시오.

피자 반죽을 오븐에 넣는 것은 오븐의 위에서부터 한 칸씩 확인하며 처음으로 피자 반죽보다 지름이 작아지는 칸을 찾아 그 윗칸에 피자 반죽을 놓는 것이다. 이를 그대로 구현하면 $O(N \times D)$가 되므로 시간 초과가 된다.

처음으로 피자 반죽보다 지름이 작아지는 칸을 찾는 것을 다시 생각해보면 오븐의 위에서 피자 반죽을 떨어트린다고 했을 때 피자 반죽이 통과하지 못하는 첫 칸을 찾는 것이 된다. 따라서 매 칸마다 현재 칸까지 통과할 수 있는 피자 반죽의 지름을 미리 구해놓고 오븐의 밑에서부터 피자 반죽이 들어갈 수 있는 칸을 찾으면 된다.

따라서 오븐의 깊이 i에 따라 통과할 수 있는 피자 반죽의 지름을 저장하기 위해 oven 배열을 정의하고 Int.MAX_VALUE로 초기화 한다. 오븐의 깊이가 1부터 D까지라고 했으므로 배열의 크기를 D + 1로 잡고 oven[0]은 사용하지 않도록 한다.

1부터 D까지에 대해 현재 칸의 지름을 입력받고 윗 칸의 지름과 비교해 더 작은 값을 oven[i]에 저장해 오븐의 맨 위에서부터 현재 칸까지 통과할 수 있는 피자 반죽의 지름을 oven[i]에 저장한다.

그 이후에 오븐에 피자 반죽을 순서대로 넣기 위해 현재 피자 반죽이 들어갈 수 있는 최대 깊이인 D를 pos에 저장한다. pizza에 오븐에 넣을 피자 반죽의 지름을 순서대로 받으며 oven[pos]과 비교해 oven[pos]의 값이 pizza에 저장된 반죽의 지름보다 작다면 현재 칸에는 피자 반죽이 들어갈 수 없는 칸이므로 oven[pos]가 pizza와 크거나 같아질때까지 pos를 1씩 감소시킨다.

그렇게 pos를 감소시키면 오븐의 깊이가 pos칸일 때 현재 피자 반죽을 놓을 수 있다는 것이므로 현재 피자 반죽을 놓았다는 뜻으로 pos를 1 감소시키고 다음 피자 반죽을 확인한다. 만약 모든 피자 반죽을 놓기 전에 pos가 1보다 작아지게 된다면 오븐에 더 이상 피자 반죽을 놓을 수 없게 되는 것이므로 pos에 -1을 대입하고 반복문을 탈출한다.

만약 반복문을 정상적으로 완수했다면 pos에 마지막 피자 반죽이 놓인 오븐의 윗칸의 깊이가 저장되어 있는 것이고, 중간에 탈출했다면 모든 피자 반죽이 들어갈 수 없다는 뜻으로 pos에 -1이 저장되어 있는 것이므로 pos + 1을 출력하면 피자 반죽이 들어간 가장 윗칸의 깊이 또는 피자 반죽이 모두 들어가지 못했다는 뜻의 0이 출력되므로 정답이 된다.

소스 코드

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun nextInt(): Int{
        nextToken()
        return nval.toInt()
    }
    val D = nextInt()
    val N = nextInt()
    val oven = IntArray(D + 1){Int.MAX_VALUE}
    for(i in 1..D){
        oven[i] = minOf(oven[i - 1], nextInt())
    }
    var pos = D
    repeat(N){
        val pizza = nextInt()
        while (pos >= 1 && oven[pos] < pizza) pos--
        if(pos < 1) {
            pos = -1
            return@repeat
        }
        pos--
    }
    println(pos + 1)
}