1756번 피자 굽기

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

dp 다이나믹 이분 탐색 binary search 오큰수 nge 오븐 피자 굽기 boj 

예제 1에서

5 6 4 3 6 2 3

이라면, 어차피 5 5 4 3 3 2 2와 같다.

이와 같은 배열을 만들어준다.(내 코드의 p)

그리고 이분 탐색을 통해 현재 q[i]가 들어갈 수 있는 가장 오른쪽(오븐으로 치면 맨 아래)으로 갈 수 있을 때까지 탐색한다.

이때, 주의할 것은 Limit인데 코드를 참고.

그리고 Stack을 이용한 풀이 방법도 있는 것 같다.

아마도 오큰수(NGE)인 것 같다.

https://hsdevelopment.tistory.com/374

#include<bits/stdc++.h>
 
using namespace std;
 
#define Max 300003
 
int n, d, p[Max], q[Max];
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    scanf("%d %d", &n, &d);
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &p[i]);
        if (i) {
            p[i] = min(p[i], p[i - 1]);
        }
    }
 
    for (int i = 0; i < d; i++) {
        scanf("%d", &q[i]);
    }
 
    // Limit는 피자 반죽이 오븐에 들어갔을 때 이후로 그 아래로는 탐색이 불가능하므로
    // 이분 탐색에서도 제한을 두었다.
    // Limit을 n - 1로하면 틀린다. 이유는 Left = mid + 1이 처음부터 계속 실행될 때 n - 2까지만 가버리기 때문이다.
    // n - 1까지 가려면 Limit는 n이 되어야한다.
    /*
    Limit이 n - 1에 대한 반례
    3 3
    1 2 3
    1 1 1
    correct : 1
    wrong : 0
    */
    int Limit = n, answer = 0;
    for (int i = 0; i < d; i++) {
        int Left = 0, Right = n - 1, Search = q[i], pivot = 0;
 
        while (Left <= Right)
        {
            int mid = (Left + Right) / 2;
 
            if (p[mid] >= Search && mid < Limit) {
                if (pivot < mid) {
                    pivot = mid;
                }
                Left = mid + 1;
            }
            else {
                Right = mid - 1;
            }
        }
 
        // 아직 끝까지 안 갔음에도 불구하고, pivot이 0이라면
        if (i < d - 1 && pivot == 0) {
            printf("0\n");
            return 0;
        }
        // 끝까지 갔고, pivot이 0이라면 p의 첫 번째 원소와 q의 마지막 원소만 비교하면 된다.
        // 끝까지 왔다는 것은 위의 if문에서 걸리지 않았다는 뜻이고, 그 전까지는 모두 들어갔다는 뜻.
        else if (i == d - 1 && pivot == 0) {
            if (p[0] < q[i]) {
                printf("0\n");
                return 0;
            }
        }
 
        Limit = pivot;
        answer = pivot + 1;
    }
 
    printf("%d\n", answer);
 
    return 0;
}