[백준 21036번] [우선순위 큐/ 갱신] Mini Market

문제 상황을 파악하기 위해서 여러번 시뮬레이션 하다보면 기존의 Amart 위치에 Imart를 짓는 것이 가장 유리하다는 것을 파악할 수 있다.

이때 우선적으로 선택되는 Imart의 위치는 다음과 같다.

 

예를 들어 Amart가 1 3 5위치에 놓여있다고 하자. 만약 3번을 선택했을 때 얻을 수 있는 사람의 수는

(1~3 사이의 사람의 수 / 2 + 1~3사이의 사람의 수 % 2) + 자기자신 + (3~5 사이의 사람의 수 / 2 + 3~5 사이의 사람의 수 / 2)라는 것을 파악할 수 있다. (단, alpha는 0 or 1)

Amart 사이에 Imart가 놓이게 될 경우, 거리가 더 가까운 위치의 mart를 가게 되므로 사이의 위치한 사람의 수 / 2가 골라지는 것은 자명하다. 다만, 추가적으로 modular연산값을 더한 이유는 거리가 같을 때 Imart를 선호하는 것을 보정하기 위함이다.

즉, 기본적으로는 각 Amart에 대해서 왼쪽, 오른쪽 값의 합이 최대가 나오는 곳부터 Imart를 지어주면 된다.

 

다만, 위 문제에서 Imart를 여러번 선택하는 과정에서 Amart 사이에 Imart를 고르는 것이 아닌, Imart와 Amart가 혼재되어 있는 상황속에서 Imart롤 선택하는 상황이 발생할 수 있게 된다. 이 경우에는 기본적으로 절반값을 가져가는 것에는 차이가 없으나, 기존의 Imart가 modular값을 통해 추가적으로 얻어간 값에 의하여 보정해야할 필요성이 발생하게 된다.

 

예를들면 다음과 같은 상황을 가정하자.

Amart가 1 3 5위치에 존재한다고 하자. 그러면 각 Amart에 대해서 (left, right)값은 다음과 같다.

-> Amart 1 : (0, 1) Amart 2: (1, 2) Amart 3: (1, 0)

 

Amart2가 left와 right를 고른 값이 가장 최대이므로 이 지점을 먼저 Imart로 만들게 되면

2,3,4지점에 위치한 사람들은 무조건 2번에 위치한 Imart로 이동하게 된다.

그러면 이 경우에 Amart1의 right와 Amart3의 left에 modular연산을 통해 더해진 1을 더 이상 쓸 수 없다.(이미 Amart 2에 할당된 고객이다.)

 

근본적으로 modular연산을 통해 나온 값을 더해준 이유가 같은 거리에 위치한 사람의 경우 Imart를 더 선호해서 보정해준 것인데

먼저 선택된 Imart의 위치에 의하여 Amart에 저장해둔 left와 right를 수정하고, 이를 기준으로 left와 right의 최댓값을 순차적으로 골라주면 된다.

 

문제를 보는 과정에서 느꼈겠지만

최댓값을 꺼내주어야 하므로, 우선순위 큐를 활용하면 된다는 것을 쉽게 파악할 수 있다.

다만, 우선순위 큐에 있는 내용물을 Imart를 선택함에 따라 갱신해주어야 한다. 따라서 이 부분을 해결하기 위해서 priority queue에 있는 정보를 저장하는 배열을 따로 만들고, priority queue에서 뽑은 값과 해당 배열에서 나온 값이 다르면 무시해주면 된다.

(정보가 업데이트를 할 경우에는 해당 배열에 정보를 업데이트하고, priority queue에도 해당 값을 넣어주면 된다.)

 

이렇게 할 경우 업데이트 되기 전 구식의 정보는 무시가 되어, 실질적으로 우선순위 큐를 업데이트 한 것과 동일한 효과를 가져올 수 있다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef pair<int, int> pii;
typedef pair<pii, int> market;

struct compare{
    bool operator()(market &d1, market &d2){
    return d1.first.first + d1.first.second < d2.first.first + d2.first.second;
    }
};

int main(void){
    fastio;
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> data;
    data.push_back(-1);
    for(int i = 1; i <= m; i++){
        int temp;
        cin >> temp;
        data.push_back(temp);
    }
    sort(data.begin(), data.end());
    data.erase(unique(data.begin(),data.end()), data.end());

    if(k >= data.size() - 1){
        cout << n << "\n";
        return 0;
    }

    priority_queue<market, vector<market>, compare> pq;
    vector<market> store_temp(data.size());
    vector<int> visited(data.size(), 0);

    for(int i = 1; i <= data.size() - 1; i++){
        int left_value, right_value;
        // Left 가능한 값 체크
        if(i == 1){
            left_value = data[1] - 1;
        }
        else{
            left_value = (data[i] - data[i - 1] - 1) / 2 +
            (data[i] - data[i - 1] - 1) % 2;
        }
        // Right 가능한 값 체크
        if(i == data.size() - 1){
            right_value = n - data[i];   
        }
        else{
            right_value = (data[i + 1] - data[i] - 1) / 2 +
            (data[i + 1] - data[i] - 1) % 2;
        }
        // 우선순위 큐와 pq체크용도 배열에 저장
        pq.push(make_pair(make_pair(left_value, right_value), i));
        store_temp[i] = make_pair(make_pair(left_value, right_value), i);
    }

    int result = 0;
    for(int i = 0; i < k; i++){
        market check_value;
        // 만족할때까지 뽑음(즉, pq안에 있는 값과 체크용도 배열에 있는 값이 같을 때까지)
        while(true){
            check_value = pq.top(); pq.pop();
            if(check_value == store_temp[check_value.second] &&
               visited[check_value.second] == 0){
                visited[check_value.second] = 1;
                break;
            }
            else continue;
        }
        result += (check_value.first.first + check_value.first.second + 1);
        int cur_index = check_value.second;
        // left check
        if(cur_index != 1){
            if((data[cur_index] - data[cur_index - 1] - 1) % 2 == 1){
                store_temp[cur_index - 1].first.second -= 1;
                pq.push(store_temp[cur_index - 1]);
            }
        }
        // right check
        if(cur_index != data.size() - 1){
            if((data[cur_index + 1] - data[cur_index] - 1) % 2 == 1){
                store_temp[cur_index + 1].first.first -= 1;
                pq.push(store_temp[cur_index + 1]);
            }
        }
    }
    cout << result << "\n";
    return 0;
}

+) 업데이트를 해줘야할 때마다 무조건 우선순위 큐에다가 넣어줬는데, 이미 방문한 배열의 경우는 이렇게 되면 망한다.

예를 들어 1 3.5에 Amart가 위치하고 3을 고름에 따라 1의 right와 5의 left가 업데이트 되는데, 5을 다시 고름에 따라 3의 right가 업데이트가 되고 다시 pq안으로 들어가서 중복 연산이 발생하는 문제가 나온다.

따라서 방문 배열을 처리해서 이미 선택한 Amart는 한번만 선택되도록 조정해야 한다.

 

+) Set으로 이 문제를 처리할 수도 있다.