[백준] 13334번: 철로 (C++)

문제 링크

13334번: 철로

---

요새 취업 시장에서 그리디 문제가 많이 나온다기에 열심히 관련 문제들을 풀고 있습니다! 👨‍💻

그리디 문제들을 풀다 보면 정렬을 사용하는 그리디와 정렬을 사용하지 않는 그리디가 있고,

여러 자료 구조 중 하나를 선택하여 푸는 그리디가 있는데, 그 중 대표적인 것이 우선순위 큐였습니다.

우선순위 큐를 이용하는 그리디 문제 중에 좋은 문제가 있어서, 하나 포스팅을 해보려고 합니다. 😊

 

풀이

정렬과 우선순위 큐를 사용해 풀이했습니다.

이 문제는 정렬과 우선순위 큐를 사용하는 그리디 문제 중에 하나이며,

대표적인 문제?는 아니지만 그리디적인 관점에서 풀어볼 만한 유형 중 하나인 문제라고 생각합니다.

 

이 문제의 핵심 포인트는 다음 두가지라 생각됩니다.

• 그리디적 접근을 위해 각 사람들을 끝점(또는 시작점)에 일치시킨 상태로 정렬한다.
• 철로 선분을 각 사람들의 끝점(또는 시작점)에 일치시키면서 선분 안에 들어가는 사람들의 수를 구한다.

여기서 주의할 점이 있습니다.

철로 선분의 범위를 끝점에 일치시켰다면, 범위를 조정한 다음에 시작점을 기준으로 포함되지 않는 사람들을 제외해야 합니다. 이 때 시작점 기준으로 사람들을 제외하기 위해서 우선순위 큐를 사용했습니다.

풀이코드

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

#define endl "\n"

vector<pair<int, int>> arr;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;

void solve() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int s, t;
    cin >> s >> t;
    if (s > t) swap(s, t);
    arr.push_back({s, t});
  }
  int d;
  cin >> d;

  auto cmp = [&](pair<int,int> a, pair<int,int> b) -> bool {
    auto [ast, aen] = a;
    auto [bst, ben] = b;
    
    if (aen == ben) return ast < bst;
    return aen < ben;
  };

  sort(arr.begin(), arr.end(), cmp);
  
  int mx = 0;
  int st = 0, en = d;
  for (auto [l, r] : arr) {
    if (r - l > d) continue;
    pq.push({l, r});
    
    // 범위 조정
    if (!(st <= l && r <= en)) {
      en = r;
      st = en - d;
    }

    // 뺄거 빼기
    while (!pq.empty() && !(st <= pq.top().first && pq.top().second <= en)) {
      pq.pop();
    }

    mx = max(mx, (int)pq.size());
  }
  cout << mx;
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#else
  ios_base::sync_with_stdio(false);
  cin.tie(0);
#endif
  solve();
  return 0;
}

 

---

부족한 글 봐주셔서 감사합니다. 🙇

풀이와 코드에 부족한 점이나 추가하면 좋을 점이 있으면 댓글 주세요!