(C++) - 백준(BOJ) 1756번 : 피자 굽기 답

www.acmicpc.net/problem/1756

1756번: 피자 굽기

이분탐색 구현방법을 생각해야하는 문제였습니다.

 

풀이방법

 1. 이분탐색은 정렬이 되었을 때 할 수 있기 때문에 구불구불한 오븐을 정리해야합니다. 위에서 봤을 때 오븐의 중간층은 넓어도 그 위의 층들이 중간층보다 좁을 때 중간층이 튀어나온 부분을 확인할 수 없습니다. 여기서 착안해서 오븐을 위에서 봤을 때 위층부터 너비의 내림차순으로 오븐 너비를 수정할 수 있습니다.

오븐 수정 후 각 층의 오븐 너비

 2. 이분탐색 시행 : 이전에 놓았던 오븐의 너비 보다 현재 오븐에 넣을 도우의 너비가 작거나 같다면 오븐에 넣을 위치는 바로 위에 올리면 됩니다. 그 외의 경우에는 이분탐색을 시행해 넣을 위치를 결정해야 합니다. 오븐의 너비가 현재 도우보다 크거나 같을 때 low = mid + 1 이외의 경우는 high = mid - 1로 하여 탐색하게 되면 오븐의 현재 너비에 피자 도우를 위치시키고 pos를 갱신해줍니다.

Code

#include <bits/stdc++.h>
using namespace std;
int oven[300001];
int dough[300001];

int main(){
    int ovenCnt, doughCnt;
    cin >> ovenCnt >> doughCnt;
    oven[0] = 0x7f7f7f7f;
    for(int i = 1; i <= ovenCnt; i++) cin >> oven[i];
    for(int i = 1; i <= doughCnt; i++) cin >> dough[i];
    for(int i = 1; i <= ovenCnt; i++) oven[i] = min( oven[i], oven[i-1] );
    int pos = ovenCnt+1;
    int old; 
    for(int i = 1; i <= doughCnt; i++){
        old = dough[i-1];
        if(!pos) break;
        if(dough[i] <= old){ pos--; continue; }
        int low = 0;
        int high=pos-1;
        while(low <= high){
            int mid = (low + high)/2;
            if(dough[i] <= oven[mid]) pos = mid, low = mid+1;
            else high = mid - 1;
        }
    }
    cout << pos <<'\n';
}

Test Case

input

2 2
2 3
4 2

답

0