[우선순위 큐] BOJ 1060 좋은 수 (C++)

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

1060번: 좋은 수

 

문제 해결 알고리즘

 

S에 속한 숫자들을 먼저 우선순위 큐에 넣고 (이 때, 들어오는 S의 원소들은 정렬되지 않았기 때문에 정렬을 꼭 해주어야한다.) 

좋은 구간의 개수는 0이긴 하지만 1로 해주어야 나중에 

 

2
1 3
3

 

같은 반례로부터 자유롭다.

 

우선순위 큐에 있는 수들은 작은 수가 먼저 나오게 정렬해준다.

 

그리고 큐에서 나온 수의 1 큰 수와 1 작은 수의 좋은 구간 개수를 구해주고 다시 그 개수와 수를 큐에 넣어주는 식으로 반복해준다. 그리고 좋은 구간의 개수가 무한대에 가까운 수라면 그냥 임의의 무한대 수를 정해서 그 값을 큐에 넣는다.

 

임의의 무한대는 여기서 나올 수 있는 좋은 구간의 최댓값이다.

 

방문 체크를 하면서 시간 복잡도를 줄여준다.

 

함정이 참 많았던 문제..

 

소스 코드

 

 

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll INF = 1e18;
map<int, bool> visited;

int main(){
    int L, n; cin >> L;
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    pq.push({0, 0});

    vector<ll> v(L+2);
    v[0] = 0;
    for(int i=1;i<=L;i++) {
        cin >> v[i];
        pq.push({1, v[i]});
        visited[v[i]] = true;
    }
    v[L+1] = 1000000001;

    sort(v.begin(), v.end());

    cin >> n;
    int cnt = 0;

    while(!pq.empty()){
        ll now = pq.top().second;

        pq.pop();

        if(now != 0) {
            cout << now << ' ';
            cnt++;
            if(cnt == n) break;
        }

        for(int i=0;i<L+1;i++){
            if(!visited[now+1] && v[i] < now + 1 && now + 1 < v[i+1]) {
                if(i == L) pq.push({INF, now+1});
                else pq.push({abs((v[i]-(now+1))*(v[i+1]-(now+1))), now+1});
                
                visited[now+1] = true;
                break;
            }
            
            if(!visited[now-1] && v[i] < now - 1 && now - 1 < v[i+1]){
                pq.push({abs((v[i]-(now-1))*(v[i+1]-(now-1))), now-1});
                visited[now-1] = true;
            }
        
        }


        
    }


}