반응형
문제 링크
13334번: 철로
입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0
www.acmicpc.net
요새 취업 시장에서 그리디 문제가 많이 나온다기에 열심히 관련 문제들을 풀고 있습니다! 👨💻
그리디 문제들을 풀다 보면 정렬을 사용하는 그리디와 정렬을 사용하지 않는 그리디가 있고,
여러 자료 구조 중 하나를 선택하여 푸는 그리디가 있는데, 그 중 대표적인 것이 우선순위 큐였습니다.
우선순위 큐를 이용하는 그리디 문제 중에 좋은 문제가 있어서, 하나 포스팅을 해보려고 합니다. 😊
풀이
정렬과 우선순위 큐를 사용해 풀이했습니다.
이 문제는 정렬과 우선순위 큐를 사용하는 그리디 문제 중에 하나이며,
대표적인 문제?는 아니지만 그리디적인 관점에서 풀어볼 만한 유형 중 하나인 문제라고 생각합니다.
이 문제의 핵심 포인트는 다음 두가지라 생각됩니다.
- 그리디적 접근을 위해 각 사람들을 끝점(또는 시작점)에 일치시킨 상태로 정렬한다.
- 철로 선분을 각 사람들의 끝점(또는 시작점)에 일치시키면서 선분 안에 들어가는 사람들의 수를 구한다.
여기서 주의할 점이 있습니다.
철로 선분의 범위를 끝점에 일치시켰다면, 범위를 조정한 다음에 시작점을 기준으로 포함되지 않는 사람들을 제외해야 합니다. 이 때 시작점 기준으로 사람들을 제외하기 위해서 우선순위 큐를 사용했습니다.
풀이코드
#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;
}
부족한 글 봐주셔서 감사합니다. 🙇
풀이와 코드에 부족한 점이나 추가하면 좋을 점이 있으면 댓글 주세요!
'Study > 알고리즘 풀이' 카테고리의 다른 글
| [프로그래머스] 정수 삼각형 (Java) (0) | 2023.10.10 |
|---|---|
| [백준] 16946번: 벽 부수고 이동하기 4 (C++) (1) | 2023.09.14 |
| [백준] 16933번: 벽 부수고 이동하기 3 (C++) (0) | 2023.09.14 |
| [백준] 14442번: 벽 부수고 이동하기 2 (C++) (0) | 2023.09.08 |
| [백준] 2206번: 벽 부수고 이동하기 (C++) (0) | 2023.09.06 |