BOJ 1756 - 피자굽기(C++)

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

1756번: 피자 굽기

 

피자마다 오븐의 모든 지름을 탐색하는 완전 탐색의 경우 O(N*M)으로 300000의 데이터들을 탐색하면 시간 초과가 발생

 

이를 해결하기 위해 그리디 알고리즘을 적용하였으며, 풀이 후 검색해보니 이분탐색으로도 해결할 수 있다하여 이분탐색으로도 풀이 해봄

 

 

풀이

오븐의 너비는 이전 위치보다 현재 위치의 너비가 크다고해도 이전위치의 너비보다 큰 피자가 들어올 수 없다

ex) {3, 4, 5}의 너비를 가진 오븐의 경우

∴ {3, 3, 3}의 너비를 가진 것과 마찬가지(오븐을 내림차순으로 정리)

오븐의 너비 배열을 변경 후 풀이

 

그리디

 - 현재 피자를 넣은 뒤, (현재 위치 - 1)의 위치부터 다음 피자의 위치를 탐색하도록 함 (O(N))

#include <iostream>

using namespace std;

int D, N;
int oven_diameter[300001], pizza_diameter[300001];
int pizza_pos[300001];

int main() {
    cin >> D >> N;
    //이전 위치의 너비보다 큰 너비는 들어올수 없으므로 배열값을 수정
    for (int i = 1; i <= D; i++) {
        cin >> oven_diameter[i];
        if (i > 1 && oven_diameter[i] > oven_diameter[i - 1])
            oven_diameter[i] = oven_diameter[i - 1];
    }
    
    for (int i = 1; i <= N; i++) {
        cin >> pizza_diameter[i];
    }

    int i=D;
    int cnt = 1;
    //역순으로 탐색하며 다음 피자에 대한 탐색을 하더라도 (이전 피자의 위치-1)에서 부터 탐색
    for (int i = D; i > 0; i--) {
        if (oven_diameter[i] >= pizza_diameter[cnt]) {
            pizza_pos[cnt] = i;
            cnt++;
        }

        if (cnt > N)
            break;
    }
    if (cnt > N)
        cout << pizza_pos[N];
    else
        cout << 0;
    
    return 0;
}

이분탐색 O(log(N))

left =1 , right=pos-1 로 하고 flag를 이용해 이분탐색의 비교(pizza_diameter[i] <= oven_diameter[mid])를 한번이라도 만족하지 못한다면 pos=0 break로 했었는데 성공하지못함(이유 모름)

 

left=0, right=pos로 하니 해결 -> oven_diameter를 0까지 탐색하게 하여 oven_diameter[0]보다 작은것에 만족하게하여 pos=0으로 만들어버리는 방법을 사용

#include <iostream>

using namespace std;

int D, N;
int oven_diameter[300001], pizza_diameter[300001];

int main() {
    cin >> D >> N;
    //오븐 너비 idx=0을 어떤 피자의 너비든 통과할 수 있는 값으로 설정
    //이후 탐색에서 피자가 오븐에 들어갈수 없는 경우에 pizza_diameter[0]에는 만족하게 만들어 pos=0으로 만들기 위해
    oven_diameter[0] = 987654321;
    for (int i = 1; i <= D; i++) {
        cin >> oven_diameter[i];
        if (oven_diameter[i] > oven_diameter[i - 1])
            oven_diameter[i] = oven_diameter[i - 1];
    }
    
    for (int i = 1; i <= N; i++) {
        cin >> pizza_diameter[i];
    }
    
    int pos = D+1;
    for (int i = 1; i <= N; i++) {
        int last_pizza = pizza_diameter[i - 1];
        if (!pos)break;
        if (pizza_diameter[i] <= last_pizza) {
            pos--;
            continue;
        }
        
        int left = 0;
        int right = pos - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            //현재 피자 너비가 mid 위치의 오븐에 가능하다면 pos를 저장하고 가능한 위치를 계속 탐색
            if (pizza_diameter[i] <= oven_diameter[mid] ) {
                pos = mid;
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
    }
    cout << pos;
    return 0;
}