문제 설명
수직선 위에 그어진 선분 길이의 총합을 출력하면 되는 문제입니다아아오아우아으ㅓ아으ㅜ아아우ㅏㅏㅏ으어ㅓ어ㅏ아.
풀이
선분의 좌표가 (-10억, 10억)이므로 좌표에 대한 배열을 사용할 수 없고 N이 최대 10만이므로 O(N^2)의 시간 복잡도로 해결할 수 없습니다.
선분들이 주어졌을 때 현재 선분과 근접한 선분과 겹치는지 확인하고 겹치면 합쳐주면 됩니다.
문제에서 친절하게 x, y좌표로 정렬을 하여 입력이 주어집니다.
선분을 차례대로 입력받으면서 현재 보고 있는 선분과 겹치면 그 선분을 합쳐서 선분을 이어 줄 겁니다.
현재 선분이 (A, B)라고 한다면 입력받은 선분이 (C, D)라고 해보겠습니다.
x, y 기준으로 정렬을 했으니 A <= C, B <= D입니다.
선분이 겹치니 합쳐 줘야 합니다. B에 B와 D의 최댓값을 대입하면 선분 (A, max(B, D))를 만들 수 있습니다.
입력받은 선분이 만약 현재 선분과 겹치지 않는다면 현재 선분의 길이를 총합에 더해주고 입력받은 선분을 현재 선분으로 보면 됩니다.
겹치지 않으니 총합에 (A, B)의 길이를 더해주고 (C, D)를 현재 선분으로 (A, B)라고 하겠습니다.
이렇게 모든 선분을 보면서 계산을 하면 합쳐진 선분들의 길이를 구할 수 있습니다!
자세한 구현 과정은 코드를 보시면 이해 안 되시는 부분도 다 이해되실 것 같습니다!!
소스 코드
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(i, a, b) for(int i=a;i<=b;i++)
using namespace std;
int main() {
FIO;
int n, ans = 0;
cin >> n;
int l, r; l = r = -1e9 - 1;
FOR(i, 1, n) {
int a, b; cin >> a >> b;
if (a > r) {
ans += (r - l);
l = a, r = b;
}
else r = max(r, b);
}
ans += (r - l);
cout << ans << '\n';
return 0;
}