이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 13334번 : '철로' 문제의 풀이 코드와 해설을 다루고 있습니다.
문제 난이도는 Solved.ac 기준 Gold II에 해당하며, 문제를 풀이하기 위해 스위핑 알고리즘에 대한 이해를 기반으로 하고 있으면 좋습니다.
스위핑 알고리즘이란, 일정 방향으로 이동하면서 데이터들을 스캔하며 문제에서 요구한 값을 계산하는 알고리즘입니다.
특정 그룹의 데이터들에 대해서 일일이 계산하면 O(N^2)의 시간이 소모되는 과정을 O(N log N)의 시간에 해결하는 등 계산 시간을 대폭 감소시킬 수 있습니다.
13334번 : 철로
길이 D인 선분 안에 포함할 수 있는 최대 선분의 수를 구하는 문제입니다.
당연히 모든 시작점과 끝점에 대해 검사를 하게되면 O(N^2)의 시간복잡도의 알고리즘이 되므로 시간 초과가 발생하게 됩니다.
스위핑 알고리즘을 통해 왼쪽부터 한 방향으로 이동하면서 최대 포함 선분 개수를 구해보도록 하겠습니다.
(참고로 다른 풀이들에서는 우선순위 큐를 활용한 사례가 많지만, 이 풀이에서는 우선순위 큐를 사용하지 않습니다.)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<pair<int, int>> Line;
for(int i=0; i<N; i++) {
int H, O; cin >> H >> O;
if(H > O) swap(H, O);
Line.push_back({H, O});
}
int D; cin >> D;
vector<pair<int, int>> Point;
for(int i=0; i<N; i++) {
if(Line[i].first + D < Line[i].second) continue;
Point.push_back({Line[i].first, 1});
Point.push_back({Line[i].second - D, -1});
}
sort(Point.begin(), Point.end());
int Cnt = 0, Ans = 0;
for(int i=0; i<Point.size(); i++) {
Cnt -= Point[i].second;
if(Cnt > Ans) Ans = Cnt;
}
cout << Ans;
}
먼저 선분들의 양 끝 점 좌표들을 입력받고, 이 때 좌표의 크기 관계가 반대로 된 것도 있으므로 적절히 swap하여 데이터들을 int pair로 입력받아줍니다.
그 다음 선분의 길이가 D보다 큰 것은 애초에 길이 D인 선분에 포함이 될 수 없으므로 넘어가줍니다.
이제 여기가 핵심 아이디어인데, 선분 D를 이동시키면서 생각하지말고 모든 선분의 길이를 D만큼 줄였다고 생각합니다. (모든 선분들의 끝점을 왼쪽으로 D만큼 평행이동시킵니다. 끝점이 시작점보다 더 왼쪽으로 가도 상관없습니다.)
그 다음 맨 왼쪽 좌표에서부터 이동하면서, 끝점을 지나면 끝점의 오른쪽에서는 그 선분을 포함하고 있는 것이므로 +1을 카운트해주고, 시작점을 지나면 그 선분을 지나친 것이므로 -1을 해주는 방식으로 카운트해주면 한 번의 스캔으로 최대 선분의 개수를 셀 수 있습니다.
그런데 위의 코드에서는 시작점을 1로, 끝점을 -1으로 pair에 저장하고 cnt에서 -= point로 처리해주고 있는 것을 볼 수 있습니다.
이것은 sort 과정에서 같은 좌표에 점이 여러 개 모였을 때 끝점을 먼저 체크하기 위해서입니다.
왜냐하면 문제에서는 길이 D인 구간에 최대로 포함할 수 있는 선분의 수를 구하라고 하였기 때문에, 카운트에 대해 + 연산을 먼저 해주어야 하기 때문입니다.
+ 또는 헷갈리지 않게 코드를 짜려면 sort 함수를 따로 구현하는 방법도 좋습니다.
풀이 코드를 제출하면 위와 같은 기록으로 정답 처리를 받을 수 있습니다.
'알고리즘 > 백준(BOJ) 문제풀이' 카테고리의 다른 글
[백준/BOJ] 14889번 : 스타트와 링크, 9184번 : 신나는 함수 실행, 1904번 : 01타일 (0) | 2022.02.20 |
---|---|
[백준/BOJ] 단계별로 풀어보기 : 기본 수학 2, 정렬 (올클리어) (0) | 2022.02.20 |
[백준/BOJ] 2533번 : 사회망 서비스(SNS) (DP) (0) | 2022.02.15 |
[백준/BOJ] 16726번 : 영과일 학회방 (이분 매칭, Platinum III) (0) | 2022.01.19 |
[백준/BOJ] 3295번 : 단방향 링크 네트워크 (이분 매칭, Platinum II) (0) | 2022.01.19 |