BOJ 1689 겹치는 선분

https://www.acmicpc.net/problem/1689

1689번: 겹치는 선분

 

https://driip.me/65d9b58c-bf02-44bf-8fba-54d394ed21e0

누적합의 확장, imos법

 

imos법이라고 불리는 트릭을 이용하는 문제입니다.

메모리 초과를 안 받는 선에서 imos법을 위한 출/입 배열을 잡을 수 있는 문제는 간단히 해결가능 합니다.

그런데 이런 문제처럼 좌표의 범위가 10억에 웃도는 경우는 좌표압축을 고려할 수 있습니다.

 

처음엔 좌표압축 대신에 그저 map 자료구조로 출/입을 기록했는데, TLE를 받았습니다.

그런데 찾아보니, 그냥 벡터에 넣고 정렬 한 뒤 스위핑으로 해결할 수 있었습니다.

 

 

#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
map<int, int> cover;


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    vector<pii> vec;
    for(int i=0; i<N; i++){
        int s, e;
        cin >> s >> e;
        vec.push_back({s, 1});
        vec.push_back({e, -1});
    }

    sort(all(vec));
 
    int cur = 0, ans = 0;
    for(int i=0; i<sz(vec); i++){
        if(vec[i].second == 1) cur++;
        else cur--;
        ans = max(ans, cur);
    }
    cout << ans;
}