백준 온라인 저지, 그리디 / 15922번: 아우으우아으이야 (파이썬 / 백준 골드문제)

문제

아우으 우아으이야!! 으어아아아아아아아ㅏㅏㅏ아아앙ㅇ아아ㅏ

수직선 위에 선분을 여러 개 그릴 거 야아아앙ㅇ아아아ㅏㅏ아아ㅏㅏ!!

선분을 겹치게 그리는 것도 가능하다아어으우어우으아아아아아아아아아이야!!!!1

선분을 모두 그렸을 때, 수직선 위에 그려진 선분 길이의 총합은 얼마아아으으우어으이으야이야!!!!

입력

첫째 줄에 수직선 위에 그릴 선분의 개수 N이 주어진다아우으 우아으이야!!. (1 ≤ N ≤ 100,000)

둘째 줄 부터 N개의 줄에 좌표를 나타내는 정수쌍 (x, y)가 주어진다으어아아아아아아아ㅏㅏㅏ아아앙ㅇ아아.

이는 [x, y] 구간 (x와 y를 포함하는 구간)에 선분을 그린다는 의미이다유아아우응아이양. 

좌표는 x가 증가하는 순으로, x가 같다면 y가 증가하는 순으로 주어진다으우오아앙아ㅓㅇ아ㅡㅇ. (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)

출력

N개의 선분을 모두 그렸을 때, 수직선 위에 그어진 선분 길이의 총합을 출력한다아아어으잉에애야우아으아이아야아아아아아아이야!!!

제한

예제 입력 1

5
-5 -2
-3 0
2 5
6 10
8 12

예제 출력 1

14

예제 입력 2

2
-1000000000 1000000000
-1 1

예제 출력 2

2000000000

힌트

접근 방법

- 첫 x와 y를 각각 start, end 변수에 저장한다.
- 이후 n개의 선분을 탐색하며 end보다 xi가 작은 경우 end의 길이를 yi로 늘린다.
- 만약 end가 xi보다 작다면 end - start를 result에 누적합한 뒤, start와 end를 xi와 yi로 초기화한다.
- 모든 탐색이 끝난 뒤, end - start를 result에 누적합한 뒤, 이를 출력한다.

코드

# https://www.acmicpc.net/problem/15922
# 접근 방법
# 첫 x와 y를 각각 start, end 변수에 저장한다.
# 이후 n개의 선분을 탐색하며 end보다 xi가 작은 경우 end의 길이를 yi로 늘린다.
# 만약 end가 xi보다 작다면 end - start를 result에 누적합한 뒤, start와 end를 xi와 yi로 초기화한다.
# 모든 탐색이 끝난 뒤, end - start를 result에 누적합한 뒤, 이를 출력한다.
n = int(input())
array = [list(map(int, input().split())) for _ in range(n)]
start, end = array[0][0], array[0][1]
result = 0
for x, y in array:
    if x <= end:
        end = max(y, end)
    else:
        result += end - start
        start, end = x, y
result += end - start
print(result)