[백준 1756] 피자 굽기 C++

www.acmicpc.net/problem/1756

1756번: 피자 굽기

 

피자 굽기는 오븐에 들어갈 피자 크기를 판단하여 오븐 안에 차곡차곡 넣고, 

오븐 크기에 따라, 들어갈 수 있는 피자 칸도 달라지게 됩니다.

 

예제 입력으로

5 6 4 3 6 2 3의 오븐 크기가 나오는데,

이부분을 좀 더 쉽게 생각하면,

5 5 4 3 3 2 2로 숫자를 바꿔서 생각할 수 있습니다.

 

피자 반죽 5가 5 6을 들어가던 5 5를 들어가던 들어갈 수 있는 크기는 정해져있습니다.

5 6 4에서 4부분을 통과하지 못하니까요. 

 

따라서, 계산하기 쉽게 5 5 4 3 3 2 2 로 변환하여 피자 순서대로 크기를 넣어서 걸리는 부분을 계산해주면 됩니다.

 

친구와 알고리즘 스터디 하면서 친구는 들어갈 수 있는 위치를 이분탐색을 통해 찾았는데,

 

저는 오븐의 맨 끝 쪽 2 2부분

에서 거꾸로 오븐을 탐색하면서 피자 위치를 하나씩 넣어보고 들어가면 cnt++해서 넣어주는 방식을 택했습니다.

이분 탐색을 이용하면 시간복잡도는 O(logN)이겠지만,

제가 사용한 거꾸로 탐색해도 O(N)으로 시간초과가 나지 않습니다.

 

#include <iostream>

using namespace std;

const int MAX = 300001;


int darr[MAX];
int narr[MAX];
int d, n;

int visit[MAX];

void solution(){
    cin >> d >> n;

    for (int i = 0; i < d; i++){
        cin >> darr[i];

        if (i != 0 && darr[i - 1] < darr[i]) darr[i] = darr[i-1];
    }

    for (int i = 0; i < n; i++){
        cin >> narr[i];
    }

    int cnt = 0;

    for (int i = d - 1; i >= 0; i--){

        if (narr[cnt] <= darr[i]){
            
            visit[cnt] = i + 1;
            cnt++;
        }

        if (cnt == n) break;   
    }   

    if (cnt == n) cout << visit[cnt - 1] << '\n';
    else cout << 0 << '\n';

}
int main(){
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    solution();

    return 0;
}