[백준] 2170번 선 긋기

문제: 2170번: 선 긋기

basic-algo-lecture/workbook/0x11.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x11.md at master · encrypted-def/basic-algo-lecture

 

#include <bits/stdc++.h>

using namespace std;

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

    int n;
    cin >> n;
    vector<pair<long long, long long>> lines(n);
    for (int i = 0; i < n; i++) {
        long long x1, x2;
        cin >> x1 >> x2;

        // first 가 항상 second 보다 작도록 설정
        if (x1 > x2)
            swap(x1, x2);

        lines[i] = { x1, x2 };
    }
    // 오름차순 정렬
    sort(lines.begin(), lines.end());

    long long sum = lines[0].second - lines[0].first; // 초기값 설정
    long long prevSec = lines[0].second;
    for (int i = 1; i < n; i++) {
        // 만약 이전 second 값이 현재 first 값보다 크다면 좌표를 (prevSec, curSecond) 로 생각하기
        if (prevSec > lines[i].first) {
            int dist = lines[i].second - prevSec;
            sum += dist > 0 ? dist : 0;
        }
        else {
            // 그게 아니면 좌표를 그냥 원래의 값으로 생각하기
            sum += lines[i].second - lines[i].first;
        }
        // 갱신
        if (prevSec < lines[i].second)
            prevSec = lines[i].second;
    }
    cout << sum;

    return 0;
}

 

입력으로 x1, x2 값이 들어온다. 항상 x1 의 값을 x2 의 값보다 작도록 설정해야 문제를 쉽게 해결할 수 있다. 그래서 만약 x1 의 값이 x2 보다 크다면 swap 하도록 했다.

 

이렇게 vector 에 값을 채운 후에는 first 값을 기준으로 오름차순 정렬한다. 나는 그리디 문제를 풀 때마다 어느 한 부분을 아예 고려 선상에서 제거해버리는 식이다. 이 문제에서는 first 값을 기준으로 오름차순 정렬하여 이를 고려 선상에서 제거해버리도록 했다. 현재의 first 값은 다음의 first 값보다 항상 작게 만든것이다.

 

그러면 이제 고려해야 하는 사항이 줄어들었다. 이제는 second 값을 기준으로 문제를 해결하면 된다. prevSec 이라는 변수를 하나 만들어서 이전 second 값을 저장하도록 한다. 근데 아무 second 값이나 저장할 수 있는 것은 아니고 지금까지 나온 second 값 중에 가장 큰 값이 저장되어야 한다.

 

만약 prevSec 값이 현재의 first 값보다 크다면 좌표를 (prevSec, curSecond) 라고 생각하면 편하다. curSecond - prevSec 한 값은 저절로 중복되는 부분의 길이를 제한것과 같다. 근데 이 값이 음수일 때는 더하면 안 되니까 삼항연산자로 걸러내었다.

 

prevSec 값이 현재의 first 값보다 크지 않다면 그냥 좌표를 원래의 좌표로 생각하면 된다. 그러면 해당 선분의 길이는 그냥 curSecond - curFirst 이다. 이렇게 sum 변수에 매 반복문마다 dist 를 더해주면 된다.

 

다음 for 문으로 넘어가기 전에 만약 현재의 second 값이 prevSec 값보다 크다면 갱신해주도록 했다.

 

마지막에 sum 을 출력해주면 문제 해결 ~_~!!