백준 2170번 선 긋기 (C++)

문제 링크 : www.acmicpc.net/problem/2170

2170번: 선 긋기

이 문제는 백준 11000번 강의실 배정과 유사한 문제이다.

그리 어려운 문제가 아닌데 처음 로직을 잘못 구현해서 여러번 틀렸다.

 

문제 풀이는 다음과 같다.

1. int-pair형 벡터에 값을 입력 받는다. 이때 주의사항이 있는데, 문제에서는 입력받는 값 x<y가 지켜진다고 했지만, 실제로는 지켜지지 않는다. 때문에 x>y인 경우에 대비하여 값을 swap하는 코드도 적어주자.

2. 벡터를 first를 기준 오름차순으로 정렬한다.

3. 벡터의 0번째 값은 별도로 변수에 저장해준다.

    st = v[0].first, ed = v[0].second;

4. 1부터 벡터의 사이즈 미만까지 for문을 돌려준다.

    for(int i=1; i<n; i++){
        if(ed>v[i].first){
            if(v[i].second>ed) ed = v[i].second;
        }
        else{
            ans += ed-st;
            st = v[i].first, ed = v[i].second;
        }
    }

이때 만약 v[i].first의 값보다 ed의 값이 크다면, 현재 선분의 길이는 이전 선분과 길이가 겹침을 의미한다.

동시에 v[i].second의 값이 ed보다 크다면, 아래와 같은 그림이 된다. 때문에 ed의 값을 v[i].seond로 갱신해준다.

만약 v[i].second의 값이 ed보다 작다면, 해당 선분은 완벽하게 이전 선분과 겹침을 의미한다. 때문에 별 다른 action을 취하지 않아도 된다.

 

5. 반대로 v[i].first의 값이 ed보다 클 경우, 해당 선분은 겹치는 곳 없이 동떨어져 있음음을 의미한다.

때문에 기존의 ed-st를 계산하여 선분의 길이를 저장해주고, 새로운 선분의 값을 st와 ed에 저장해준다.

 

6. 벡터의 모든 계산이 끝났으면 마지막 남은 선분의 길이를 계산해서 더해주고 답을 출력한다.

    ans += ed - st;
    cout << ans << "\n";

#include <iostream>
#include <vector>
#include <algorithm> 
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n = 0, st=0, ed=0, temp = 0;
    long long ans = 0;
    cin >> n;
    vector<pair<int,int>> v(n,{0,0});

    for(int i=0; i<n; i++){
        cin >> st >> ed;
        if(st>ed){
            st = temp;
            st = ed;
            ed = temp;
        }
        v[i] = {st,ed};
    }
    sort(v.begin(),v.end());
    st = v[0].first, ed = v[0].second;
    for(int i=1; i<n; i++){
        if(ed>v[i].first){
            if(v[i].second>ed) ed = v[i].second;
        }
        else{
            ans += ed-st;
            st = v[i].first, ed = v[i].second;
        }
    }
    ans += ed - st;
    cout << ans << "\n";
    return 0;
}