백준 2170번 c++

문제 출처

백준 2170번

문제

매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.

이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.

입력

첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.

출력

첫째 줄에 그은 선의 총 길이를 출력한다.

테스트 케이스

4
1 3
2 5
3 5
6 7

answer:
5

알고리즘 분류

Line Swapping

풀이

main 부분입니다. 선을 그은 횟수 N을 입력 받고 벡터 Line을 크기 N으로 초기화해줍니다. pair 자료형을 사용해 시작점을 first, 끝점을 second에 저장해주고 함수 Swapping을 실행합니다.

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

    cin >> N;
    vector<pair<int, int>> Line(N);
    for (int i = 0; i < N; i++)
        cin >> Line[i].first >> Line[i].second;
    Swapping(Line);
    return 0;
}

Swapping 함수 부분입니다. 매개변수로 vector<pair<int,int>>를 참조해 받습니다. 시작점이 작은 선부터 그어야 빼먹는 부분이 없으므로 Line을 오름차순으로 정렬해줍니다. Left와 Right에 각각 Line[0] 값을 저장해준 뒤 반복문을 돌립니다. 만약 Right >= Line[i].first라면 선이 겹치는 경우이므로 Right에 Line[i].second을 저장해줍니다. 아니라면 선이 겹치지 않으므로 answer 값을 업데이트 해준 뒤 Left와 Right을 재설정해줍니다.

	void Swapping(vector<pair<int, int>>& Line)
{
    sort(Line.begin(), Line.end());
    int answer = 0;
    int Left = Line[0].first;
    int Right = Line[0].second;

    for (int i = 1; i < N; i++)
    {
        if (Right >= Line[i].first)
        {
            if (Right < Line[i].second)
                Right = Line[i].second;
        }
        else
        {
            answer += Right - Left;
            Left = Line[i].first;
            Right = Line[i].second;
        }
    }
    answer += Right - Left;
    cout << answer;
}

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int N;

void Swapping(vector<pair<int, int>>& Line)
{
    sort(Line.begin(), Line.end());
    int answer = 0;
    int Left = Line[0].first;
    int Right = Line[0].second;

    for (int i = 1; i < N; i++)
    {
        if (Right >= Line[i].first)
        {
            if (Right < Line[i].second)
                Right = Line[i].second;
        }
        else
        {
            answer += Right - Left;
            Left = Line[i].first;
            Right = Line[i].second;
        }
    }
    answer += Right - Left;
    cout << answer;
}


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

    cin >> N;
    vector<pair<int, int>> Line(N);
    for (int i = 0; i < N; i++)
        cin >> Line[i].first >> Line[i].second;
    Swapping(Line);
    return 0;
}