[백준] 1756번: 피자 굽기 - C++

문제

월드피자 원주 지점에서 N개의 피자 반죽을 오븐에 넣고 구우려고 한다. 그런데, 월드피자에서 만드는 피자 반죽은 지름이 제각각이다. 그런가하면, 월드피자에서 사용하는 오븐의 모양도 몹시 오묘하다. 이 오븐은 깊은 관처럼 생겼는데, 관의 지름이 깊이에 따라 들쭉날쭉하게 변한다. 아래는 오븐의 단면 예시이다.

피자 반죽은 완성되는 순서대로 오븐에 들어간다. 이렇게 N개의 피자가 오븐에 모두 들어가고 나면, 맨 위의 피자가 얼마나 깊이 들어가 있는지가 궁금하다. 이를 알아내는 프로그램을 작성하시오.

 

입력

첫째 줄에 오븐의 깊이 D와 피자 반죽의 개수 N이 공백을 사이에 두고 주어진다. (1 ≤ D, N ≤ 300,000) 둘째 줄에는 오븐의 최상단부터 시작하여 깊이에 따른 오븐의 지름이 차례대로 주어진다. 셋째 줄에는 피자 반죽이 완성되는 순서대로, 그 각각의 지름이 주어진다. 오븐의 지름이나 피자 반죽의 지름은 10억 이하의 자연수이다.

 

출력

첫째 줄에, 마지막 피자 반죽의 위치를 출력한다. 오븐의 최상단이 1이고, 최하단 가장 깊은 곳이 D이 된다. 만약 피자가 모두 오븐에 들어가지 않는다면, 0을 출력한다.

---

별거 아니라 생각했는데 골드 5인데는 이유가 있던 문제.. 아무 생각 없이 이중 for문을 사용해서 쉽게 풀려고 하면 2초의 넉넉한 시간임에도 D, N의 숫자 범위때문에 시간초과가 난다.

 

이런식으로 힌트가 주어지는데, 여기서 생각해야 될 점은 아무리 지름이 6인 구간이 존재하여도, 최상단의 지름이 5이면 지름이 6 이상의 피자는 들어갈 수 없다는 것이다. 따라서 지름이 좁아지는 대로 아래 사진과 같은 구조의 오븐이라고 생각해준 뒤, 최하단부터 현재 피자의 지름 크기와 비교해준다.

이분탐색으로 푸는 방법도 있으나, (잘 모르는 관계로ㅠㅠ)간단하게 O(N) 방식으로만 풀었다.

 

코드

#include <cstdio>
#include <vector>

using namespace std;

int main(void) {
    int D, N;
    scanf("%d %d", &D, &N);

    vector<int> oven(D);
    vector<int> pizza(N);
    for(int i = 0; i < D; i++) {
        scanf("%d", &oven[i]);
        if(i != 0 && oven[i - 1] < oven[i]) oven[i] = oven[i - 1];
    }

    for(int i = 0; i < N; i++) {
        scanf("%d", &pizza[i]);
    }

    int count = 0;
    for(int i = D - 1; i >= 0; i--) {
        if(pizza[count] <= oven[i]) count++;
        
        if(count == N) {
            printf("%d\n", i + 1);
            return 0;
        }
    }

    printf("0\n");
    return 0;
}