[백준] 피자 굽기(1756)

문제 링크 : [백준] 피자 굽기(1756)

문제 설명

m개의 피자 반죽을 오븐에 넣는데, 오븐은 스택처럼 되어있습니다.
각 깊이별로 담을 수 있음 피자 반죽의 너비가 제한되어 있어서, 피자 반죽을 넣을 경우, 피자 반죽보다 작은 너비의 깊이를 만나면, 그 위에 피자가 놓이게 됩니다.
마지막 피자가 어느 깊이에 놓이는지를 구하여야 합니다.

입력

N(오븐의 깊이, 1 <= N <= 300,000)
M(피자 반죽의 갯수, 1 <= M <= 300,000)
O_i(각 오븐의 깊이마다 담을 수 있는 피자 반죽 너비, 1<= O_i <= 10억)
P_i(피자 반죽의 너비,1<= O _i <= 10억)

7 3
5 6 4 3 6 2 3
3 2 5

출력

2

카테고리

#구현 #이분탐색

시간 복잡도 상한

O(NlogN)

해결 방법

1. 아무 생각 없이, 위에서부터 차례로 넣을 수 있는 깊이를 구하면 O(N²)이 되어 TLE가 됩니다.
2. 피자가 쌓이는 오븐의 깊이를 생각해보면, 피자의 너비보다 작은 너비를 가지는 오븐의 깊이 중 가장 낮은 깊이를 찾으면 됩니다.
   2-1. 예제에서 보면, 5를 넣는 경우, 깊이가 3에서 피자의 너비 5보다 작은 4가 처음 나오게 됩니다.
   2-2. 그렇기 때문에 깊이 2에 쌓이게 됩니다.
3. 그렇다면, 각 깊이별로 필요한 데이터는 현재 너비보다는 현재 깊이까지 중 가장 작은 너비를 구하면 됩니다.
   3-1. 위에서 현재 너비보다 작은 너비가 있었다면, 그 깊이때문에 어차피 더 넓은 피자 반죽은 들어 올 수 없기 때문에, 필요 없는 값이 됩니다.
4. 깊은 곳에서 위로 올라오면서, 최소 너비가 피자 반죽 너비보다 크거나 같은 깊이까지 반복적으로 찾아 올라오면서 피자 반죽이 담길 위치를 찾습니다.
5. 여기까지 하면 시간복잡도는 O(N)이 됩니다.
6. 잘 생각해보면 오븐의 최소 너비 데이터는 비오름차순으로 구성됩니다.
7. 그렇기때문에, 4번 위치를 이분탐색으로 구하면 더욱 빠르게 구할 수 있습니다.(O(logN))
8. 하지만 O(N)의 시간 복잡도로도 풀리기 때문에 오버스펙인거 같아 풀이 방법은 거기까지 하지는 않았습니다.

시간복잡도

O(N)

코드

#include<iostream>
#include<algorithm>
using namespace std;
int n,m,d[300001]={2000000000},i,k;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(i=1;i<=n;i++)cin>>k,d[i]=min(d[i-1],k);
    while(m--){
        cin>>k;
        while(n>0&&d[n]<k)n--;
        n--;
    }
    cout<<(n>=0?n+1:0);
}