백준 32069 가로등 C++

요약

 

L이 너무 큰수고, K는 작다.

가로등을 기준으로 BFS를 돌리면 쉽게 답을 구할 수 있다.

그런데 중복처리를 실수하면 틀리기 쉽고 long long 형을 사용해야한다.

 

답

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#define ll long long
using namespace std;
int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  ll l,k,n;
  vector<ll> ans;
  set<ll> s;
  cin>>l>>n>>k;
  vector<ll> v(n,0);
  for(int i=0;i<n;++i) cin>>v[i];
  priority_queue<pair<ll,ll>> q;
  for(int i=0;i<n;++i){
    q.push({0,v[i]});
    s.insert(v[i]);
  }
  while(!q.empty()){
    if(ans.size()==k) break;
    ll val=-q.top().first;
    ll order=q.top().second;
    q.pop();
    ans.push_back(val);
    ll nextLeft=order-1;
    ll nextRight=order+1;
    if(nextLeft>=0&&s.count(nextLeft)==0){
      q.push({-(val+1),nextLeft});
      s.insert(nextLeft);
    }
    if(nextRight<=l&&s.count(nextRight)==0){
      q.push({-(val+1),nextRight});
      s.insert(nextRight);
    }
  }
  for(int i=0;i<ans.size();++i) cout<<ans[i]<<"\n";
}