백준 15922. 아우으 우아으이야!!

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

15922번: 아우으 우아으이야!!

 

문제와 상당히 상관없는 제목이다 ㅋㅋ

 

수직선 위에 여러개의 선분을 그려 (겹칠수 있다) 총 선분의 길이를 구하는 문제다.

선분은 좌표는 x가 증가하는 순으로, x가 같다면 y가 증가하는 순으로 이미 정렬이 되어 주어진다.

 

총 세가지 케이스가 있다.

1. 선분 두개의 일부분이 겹치는 경우 
2. 다음 선분이 이전 선분에 완전히 포함되는 경우 
3. 이전 선분과 다음 선분이 완전히 떨어져있는 경우 

 

1번) 다음 선분을 입력받아서 다음 선분의 x값이 현재 그리고 있는 선분의 끝보다 작고 다음 선분의 y값이 현재 그리고 있는 선분의 끝보다 크다면 두선분의 일부분이 겹치므로 현재 그리고 있는 선분의 끝을 갱신한다. (현재 그리고 있는 선분의 시작은 그대로)

 

2번) 다음 선분의 x값이 현재 그리고 잇는 선분의 끝보다 작고 y값도 현재 그리고 있는 선분의 끝보다 작다면 완전히 포함되므로 무시.

 

3번) 그 외의 경우는 이전 선분과 다음 선분이 완전히 떨어져 있는 경우이므로 지금까지 만들어진 선분의 길이를 선분길이의 총합에 더하고,

새로운 선분을 시작한다.

 

#include <iostream>
using namespace std;

int n;

int main()
{
    cin >> n;

    long long sum = 0;
    long long begin, end;
    cin >> begin >> end;
    for(int i = 1; i < n; i++)
    {
        long long a, b;
        cin >> a >> b;

        // 선분 두개의 일부분이 겹치는 경우
        if(a < end && b > end)
        {
            end = b;
        }
        // 두번째 선분이 첫선분에 완전히 포함되는 경우
        else if(a < end && b <= end)
        {
            continue;
        }
        // 첫선분과 두번째 선분이 떨어져 있는 경우
        else
        {
            long long length = abs(end - begin);
            sum += length;
            // 갱신
            begin = a;
            end = b;
        }

        //cout << begin << ' ' << end << endl;
    }
    // 반복문 내부에서 더하지 못한 마지막 선분까지 더한다
    sum += abs(end-begin);

    cout << sum;


}