[ 백준 2170 ] 선 긋기 (C++)

백준의 선 긋기(2170) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

그어진 선의 총 길이를 구해야 하는 문제이다.

먼저 주어진 예제입력을 가지고 진행을 해보자.

예제입력으로 주어지는 좌표들을 그림으로 나타내보면 다음과 같다.

.

위와 같이 표현할 수 있다. 그리고 선분은 본인이 임의로 A, B, C, D라는 이름을 붙여주었다.

그리고 이제부터 문제를 진행해보자.

#1. 한번에 그을 수 있는 선분들

위의 4개의 선분들을 직접 펜으로 그려본다고 생각을 해보자. 그리고 이 때, 펜을 떼지 않고 한번에 그릴 수 있는

선분은 무엇이 있을까 ??

바로 A , B , C 이다. A, B , C 이 3개의 선분은 펜을 한번도 떼지 않고 한번에 그릴 수가 있다.

1번 점에서 펜으로 그리기 시작해서 5번 점까지 한줄로 쭉 긋는다면, 1번 점에서 5번점까지 연결된 하나의 선분이 그려질 것이고 이 하나의 선분 안에는 A , B , C 모두 포함되어 있을 것이다.

즉, 우리는 1번 점부터 5번 점을 잇는 길이가 4인 하나의 선분을 통해서 A , B , C 를 모두 그을 수가 있다.

#2. 한번에 그을 수 없는 선분들

#1의 과정과는 달리 반드시 펜을 한번 이상은 떼어야만 그릴 수 있는 선분 또한 존재할 것이다.

바로 D 선분이다. A, B, C선분을 한번에 그릴 수 있었듯이, D선분도 1번 점부터 7번 점까지 한번에 긋는다고 가정하면

입력으로 주어지지 않는 5 - 6번 점을 잇는 선분이 발생해 버리기 때문에 절대로 한번에 그을 수가 없다.

따라서 반드시 한번 이상은 펜을 떼어야만 그을 수 있는 선분이다.

그럼 지금부터는 #1과 #2의 이야기를 왜 했는지 이야기해보자.

선분은 중첩되는 선분이 있을 수 있고, 그 중첩되는 선분은 한번 그은것으로 계산을 한다고 했다.

즉, #1의 과정처럼 한번에 그을 수 있는 선분들이 있다면, 그리고 이를 통해서 위에서 1번점에서 5번점까지 잇는 선분을 하나 그리면 A, B, C에 해당하는 선분들을 모두 그을 수 있다라는 것을 판단했듯이, 특정 A번 점에서 B번 점까지 잇는 선분을 그음으로써 어떠어떠한 선분들을 한번에 해결할 수 있는지 알 수 있다면, 그 길이는 B - A로 간편하게 구할 수 있게 될 것이다.

또한, #2의 과정을 통해서 한번에 그을 수 없는 선분들이 있다면, 또 다르게 한번에 그을 수 없는 선분들 중에서도 또 중첩되는 선분들을 #1의 과정처럼 구함으로써 그 길이를 쉽게 구할 수 있을 것이다.

따라서 지금까지 위와 같은 이야기를 한 것이다.

그럼 이제 보다 프로그래밍 적으로 접근하기 위해서 #1의 과정을 조금 더 구체적으로 알아보자.

.

이 그림에서 우리는 이미 A, B, C 3개의 선분들은 한번에 그을 수 있다는 것을 알고 있다.

그럼 이를 이제 눈으로 판단하는 것이 아니라, 어떤 이유에서 그것이 가능한지 알아보자.

가장 먼저, 선분 A와 선분 B를 어떤 이유에서 한번에 그을 수 있는지 생각을 해보자.

A의 시작점은 '1'이고 A의 도착점은 '3'이다. 그럼 현재까지 설정되어 있는 도착점은 '3'이 될 것이다.

B의 시작점은 '2'이고 B의 도착점은 '5'이다. 그리고 이 선분을 이제 A선분과 이어서 그릴 수 있는지, 즉, 펜을 떼지 않고

한번에 그릴 수 있는지 판단해보자.

B의 시작점은 '2'이다. 현재 설정되어 있는 도착점은 '3'이다. 즉 ! 지금 새로 그리고자 하는 선분의 시작점이, 현재 설정되어 있는 도착점보다 더 작은 위치에 존재한다. 따라서 선분을 이어서 그릴 수 있다는 것이다.

그럼 이 때 도착점은 어느 지점으로 설정이 될까 ??? 선분 B를 A에 이어서 한번에 그리기 때문에 도착점은 'B'의 도착점인 '5'가 될 것이다. 하지만 ! 반드시 이어서 그린다고 해서 그 다음 선분의 도착점이 도착점으로 설정되는 것은 아니다.

예를 들어서 A가 1번부터 6번까지 잇는 선분이고, B가 2번부터 5번까지 잇는 선분이라고 가정해보자.

동일한 원리로, B의 시작점인 '2'가 현재 설정되어 있는 'A'의 도착점인 '6'보다 더 작은 값이므로 한번에 그릴 수 있다고 판단을 하겠지만, 도착점은 그대로 '6'일 것이다. 왜냐하면, B선분의 도착점인 '5'보다 '6'이 더 큰 값이기 때문에, '6'번점까지는 펜을 떼지 않고 그릴 수 있다는 것을 의미하기 때문이다.

마찬가지로 C도 한번에 그릴 수 있다고 판단할 것이다.

마지막으로 D에 대해서 생각을 해보자. 선분 C까지 그리면서 설정되어 있는 도착점은 '5'가 될 것이다.

이 때, 선분 D를 긋는다고 생각해보자. D의 시작점은 '6'이다. 즉 ! 현재 설정되어 있는 도착점보다 새로 그으려는 선분의 시작점이 더 크기 때문에 이는 한번에 그릴 수 없음을 의미한다.

따라서, 이 때는 기존에 그렸던 선분의 길이를 계산한 후에, 새로운 시작점과 도착점을 설정해 주면 된다.

기존에 그렸던 선분의 길이는 어떻게 계산을 할까 ?? 시작점은 '1'이고 도착점은 '5'였기 때문에 길이는 5 - 1 = 4 로 간단하게 계산이 가능하다.

이 후, 선분 D를 위해서 시작점을 '6' 도착점을 '7'로 새로 설정한 후에 이 과정을 모든 선분에 대해서 반복해 주면 된다.

[ 소스코드 ]

#include <iostream>
#include <algorithm>
 
#define endl "\n"
#define MAX 1000010
#define INF 1000000010
using namespace std;
 
struct LINE
{
    int Start;
    int End;
};
int N;
LINE Line[MAX];
 
int Max(int A, int B) { return A > B ? A : B; }
 
bool Compare(LINE A, LINE B)
{
    if (A.Start < B.Start) return true;
    return false;
}
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> Line[i].Start >> Line[i].End;
    }
}
 
void Solution()
{
    sort(Line + 1, Line + N + 1, Compare);
    int Answer = 0;
    int Left = -INF;
    int Right = -INF;
    
    for (int i = 1; i <= N; i++)
    {
        if (Line[i].Start <= Right)    Right = Max(Right, Line[i].End);
        else
        {
            Answer += Right - Left;
            Left = Line[i].Start;
            Right = Line[i].End;
        }
    }
    Answer += Right - Left;
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}