[C++] 백준 1270번 : 선 긋기

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

 

 

[접근]

4
1 3
2 5
3 5
6 7

예제 입력값이 다음과 같다고 해보자

 

밑의 코드에서는 start,end를 -1000000001으로 설정했다.  

1 3이 입력되고 나면 start, dest값이 각각 1,3으로 설정된다. 그 후 2 5가 입력된다. 

그럼 1 3과 2 5는 겹치는 부분이 발생한다. 입력받은 값을 s1, d1이라고 해보자 

겹치는 경우는 dest보다 s1가 작은 경우에 발생한다. 이 경우에는 끝값(dest)를 갱신해주면 된다. 

3 5도 마찬가지다.

 

6 7 은 겹치는 부분이 없다.

-> 그럼 이제껏 입력받았던 값(start,dest)의 차이를 maxcount라는 변수에 더해주고 start,dest값을 6 7로 갱신해 새롭게 연결되는 선에 대한 값을 구한다.

 

 

 

[코드]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector <pair<int, int>>v;
int n;

void solve (){	
    int maxcount= 0;
    int start = -1000000001;	
    int dest = -1000000001;	

    for (int i = 0; i < n; i++){
        int s = v[i].first;
        int d = v[i].second;
        
        if (s <= dest) dest = max(dest,d);
        else
        {
          maxcount += dest - start;
          start = s;
          dest = d;
        }
    }
    maxcount += dest - start;

    cout << maxcount;
}

int main (){
    ios_base::sync_with_stdio (false);
    cin.tie (NULL);
    cout.tie (NULL);

    cin>>n;
    
    for(int i=0;i<n;i++){
        int x, y;
        cin>>x>>y;
        v.push_back(make_pair(x,y));
    }
    sort (v.begin(), v.end());
    
    solve();
    return 0;
}