백준 1756번 피자 굽기 c++ 풀이

문제

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

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

입력

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

출력

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

예제 입력 1 복사

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

예제 출력 1 복사

2

힌트

 

문제의 핵심인 오븐의 지름을 감소하는 크기만큼 설정하는 것은 떠올렸으나 이중 for문으로 풀어서 시간초과가 났던 문제이다.

그리디로 하나의 for문만을 이용해야 풀리는 문제이다.

 

- 틀린 풀이

#include <bits/stdc++.h>

using namespace std;

int oven[300001];
int visited[300001];

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

    int d, n;
    int tempOven;
    cin >> d >> n;


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

        if (oven[i] > tempOven) {
            oven[i] = tempOven;
        }

        tempOven = oven[i];
    }

    int ans = 0;
    int pizzaTopIndex = 0;

    for (int i = 0; i < n; i++) {
        int pizzaDiameter;
        cin >> pizzaDiameter;

        for (int i = 0; i < d; i++) {

            if (oven[i] >= pizzaDiameter && visited[i] == 0) {
                continue;
            }

            if (oven[i] >= pizzaDiameter && visited[i] == 1) {
                ans++;
                visited[i - 1] = 1;
                pizzaTopIndex = i;
                continue;
            }

            if (oven[i] < pizzaDiameter && i != 0) {
                ans++;
                visited[i - 1] = 1;
                pizzaTopIndex = i;
//                cout << oven[i-1] << " " << i  << "\n" ;
                break;
            }



        }


    }

//    cout << "\n";
//    cout << ans << "\n";
    cout << pizzaTopIndex << "\n";


    return 0;
}

 

 

- 정답 풀이

 

피자오븐의 역순부터 피자의 순서대로 넣어보며 크기가 맞다면 pizza의 마지막 위치를 기록하고 출력하는 풀이이다.

#include <bits/stdc++.h>

using namespace std;

int oven[300001];
int pizza[300001];
int visited[300001];
int d, n;


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

    int tempOven;
    int pizzaTopIndex;
    cin >> d >> n;


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

        if (oven[i] > tempOven && i > 0) {
            oven[i] = tempOven;

        }
        tempOven = oven[i];

    }

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


    int cnt = 0;


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

        if (oven[i] >= pizza[cnt]) {
            pizzaTopIndex = i + 1;
            cnt++;
        }
        if (cnt == n) {
            break;
        }
    }

    if (cnt == n) {
        cout << pizzaTopIndex << "\n";
    } else {
        cout << 0 << "\n";
    }


}