[코드트리 조별과제] +1 -1 Technique

어제 해봤는데 여기서 틀렸다. 아쉽다 아래 문제의 응용문제가 나왔는데 못풀었다.

기본 개념

1차 수직선 상에 n개의 선분이 주어졌을 때, 
x = k 직선과 만나는 서로 다른 선분의 수는 몇 개인지를 판단하는 
프로그램을 작성해보세요.
단, 주어지는 x 좌표는 모두 다름을 가정해도 좋습니다.

 

문제를 가시적으로 나타내면 2개라는 것을 쉽게 알 수 있다. 이 가시성을 컴퓨터 알고리즘으로 쉽게 나타내기 위해서는 

다음과 같이 시작점에 +1, 끝 점에 -1을 하는 방법이 있다.

K를 기준으로 그보다 왼쪽에 있는 점들을 생각하여 만약 끝 점이 k보다 작다면 k와 겹치지 않으므로 시작점의 값 +1 + 끝점의 값 -1을 하므로 0이된다.

K를 기준으로 그보다 시작점이 오른쪽에 있는 점 또한 마찬가지이며 만약 겹치는 점이 생길 경우 시작점이 +1이므로 겹치는 구간 +1를 할 수 있다.

이렇게 된다면 특정한 구간 및 점에 겹치는 구간의 개수를 2 * N(시작점, 끝점)으로 계산할 수 있다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, chk, ans;
vector<pair<int, int>>v;
int main() {
    cin>>n;
    for(int i=0; i<n; i++) {
        int l, r; cin>>l>>r;
        v.push_back(make_pair(l, 1));
        v.push_back(make_pair(r, -1));
    }
    sort(v.begin(), v.end());
    for(auto point : v) {
        chk += point.second;
        ans = max(ans, chk);
    }
    cout<<ans;
    return 0;
}

이를 응용해서 가장 많이 겹치는 구간을 다음과 같이 구할 수 있다.

시작점은 무조건 +1, 끝점은 무조건 -1이라는 점을 이용해서 해당 정보를 pair vector에 집어넣고 정렬한 후에 순차탐색하는 방법으로 구현했다.

 

응용1 ) 구간의 총 개수

모든 구간을 실선으로 연결한다면, 구간이 끊어지는 경우가 발생할 수 있다.

이런 경우 구간이 끊어지는 개수를 이용해서 서로 다른 구간의 수를 구할 수 있다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, chk, ans;
vector<pair<int,int>>v;
bool cmp(pair<int,int>&a, pair<int,int>&b) {
    if(a.first == b.first)
        return a.second > b.second;
    else return a.first < b.first;
}
int main() {
    cin>>n;
    for(int i=0; i<n; i++){
        int l, r; cin>>l>>r;
        v.push_back({l, 1});
        v.push_back({r, -1});
    }
    sort(v.begin(), v.end(), cmp);
    for(int i=0; i<v.size(); i++) {
        if(i==0) chk += v[i].second;
        else {
            chk += v[i].second;
            if(chk == 0) ans += 1;
        }
    }
    cout<<ans;
    return 0;
}

 

chk의 값은 구간에 겹친 실선의 수를 의미한다.

실선의 수는 [0, ~)의 값이고, 양의 정수에서 0이 되는 순간이 서로 다른 구간이 되는 경우이다. ( 무조건 서로 다른 좌표가 들어온다는 가정. 같은 좌표가 들어온다면 문제의 정의에 따라 달라짐.)

그러므로 chk가 0이되는 순간 서로 다른 구간의 수를 1씩 늘려주면 된다.