[15922] - 아우으 우아으이야!!

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

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

접근 방법

선분의 시작점과 끝점이 정렬된 상태로 주어지니, 이전 선분에 대해 현재 선분이 그 안에 있는지, 걸쳐 있는지, 나와있는 지 판별해서 조건을 걸었다가 실패.

스위핑 알고리즘 - 이전 끝점이 시작점 보다 작으면 갱신, 아니면 이전끝점, 현재 끝점 비교 해서 큰값을 비교

 

문제 풀이

• 이미 주어진 입력이 정렬 되있으므로 0번 인덱스의 시작과 끝점을 start와 end에 넣어줌
• 1번 인덱스 부터 반복문을 돌며 이전값의 끝점이 현재의 시작점 보다 작으면 이어지지 않고 끊어져 있다는 소리니 start와 end 갱신
• 아니면 안에 있거나 겹쳐있다는 소리니 끝값을 비교해서 넣어주기
• 반복문 탈출 후 계산이 안된 시작점과 끝점이 있으니 계산 후, 출력

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Baekjoon.Gold
{
    class _15922
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[][] arr = new int[n][];
            for (int i = 0; i < n; i++)
                arr[i] = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            int start = arr[0][0];
            int end = arr[0][1];
            long sum = 0;

            //스위핑 알고리즘
            for (int i = 1; i < n; i++)
            {
                if (end < arr[i][0])
                {
                    sum += end - start;
                    end = arr[i][1];
                    start = arr[i][0];
                }
                else
                    end = Math.Max(end, arr[i][1]);
            }

            sum += end - start;
            Console.WriteLine(sum);
        }
    }
}