[백준] 1756. 피자 굽기

문제

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

풀이

뭔가 문제 자체는 어렵지는 않은데 시간이 오래 걸렸다. 문제를 딱 보면 이중 for문은 당연히 30만 * 30만으로 시간초과가 날 것이다. 이분탐색으로 풀어야하나 싶었는데 아쉽게도 오븐이 정렬된 형태가 아니다. 문제를 잘 보면 어떤 반죽이 특정 위치에서 걸려버리면 그 밑은 값이 어떻게 나오든 상관이 없어진다. 가령

5

6

4

3

6

2

3

지름의 크기가 위와 같을 때 반죽 4짜리는 4번째에서 걸려버린다. 이게 뭘 의미하냐, 예를 들어 깊이가 3인 곳의 지름은 4인데, 그 밑인 깊이가 4, 5, 6, 7은 지름이 4보다 커도 어차피 통과할 수 있는 반죽은 지름이 4이하인 반죽이다. 즉 특정 위치의 밑에 있는 것들은 그 위치의 지름보다 작거나 같아야한다. 따라서 위의 지름을 아래와 같이 바꿀 수 있다.

5

5

4

3

3

2

2

어차피 2번째의 6은 5보다 작거나 같은 반죽은 전부 통과시킬 수 있고, 6보다 큰 반죽은 애당초 첫번째에서 걸려버릴 것이므로 5라고 바꿔도 다를 바 없다. 다른 것들도 마찬가지로 생각해서 바꿔줄 수 있다.

수학적인 아이디어는 위와 같고 이제 만들어진 반죽을 차례로 돌면서 오븐에 넣어보자. 문제에선 3 2 5 짜리 반죽을 넣었다. 이 때, 맨 밑에서부터 탐색해야 중간에 걸렸는지 알 수 있게 되므로 밑에서부터 탐색하도록 만들자. 그렇다면 반죽 3은 6번째에 걸려서 5 위치에 있을테고, 반죽 2는 그 위에 올려질 것이다. 마지막 반죽 5는 3번째에 걸려서 2 위치에 있을 것이다. (문제의 힌트를 보면 이해가 될 것이다.)

즉 맨 아래서부터 탐색하되, 어디서 걸리는지 체크하는 시작점은 최근 반죽을 넣었을 때 걸리는 지점이 될 것이다.

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;

long blocked;


int main(){
    
    int D, N; cin >> D >> N;
    long dough[300001];
    long oven[300001];

    blocked = D + 1;
    long mini = 1000000001;
    long minoven = 1000000001;

    for(int i = 1; i <= D; i++){
        long t; cin >> t;
        minoven = min(t, minoven);
        oven[i] = minoven;
        
    }

    for(int i = 1; i <= N; i++){
        cin >> dough[i];
        mini = min(dough[i], mini);
    }
    // 해당 반죽이 이전 반죽보다 작으면 그 위에 살포시 얹으면 된다. 그리고 걸린 마지막 지점은 위로 한칸 올라가게 된다.
    for(int i = 1; i <= N; i++){
        if(i != 1 && dough[i] <= dough[i - 1]){
            blocked--;
        }
        // 이전 반죽보다 크다면
        else{
            // 맨 마지막으로 걸린 지점부터 맨 위까지 쭉 탐색해서
            for(int j = blocked - 1; j >= 1; j--){
                // 오븐보다 반죽이 더 클 경우 위로 한칸씩 계속 올려준다. 즉 반죽이 통과되다가 걸리는 지점을 밑에서부터 찾아주는 것이다.
                if(oven[j] < dough[i]){
                    blocked--;
                }
                // 쭉 올리다 오븐의 반지름이 더 커지게 되면 해당 지점까지는 통과된 것이다.
                else break;
            }
            // 특정 위치에서 걸린 것이므로 반죽은 그 위치보다 한칸 위에 얹혀있을 것이다.
            blocked--;
        }
    }
    // 걸린 지점이 0보다 작거나 같아지게 되면 피자가 오븐 안에 전부 들어가지 못한 것이다.

    if(blocked <= 0) blocked = 0;
    cout << blocked;
    return 0;
}