BOJ/백준-15922-python

문제📖

풀이🙏

• 출제자가 술마시고 만든 문제인것같다.
• 첫째 줄에 수직선 위에 그릴 선분의 개수 N이 주어진다.
• 둘째 줄 부터 N개의 줄에 좌표를 나타내는 정수쌍(x,y)가 주어진다.
• 이는 (x,y)구간에 선분을 그린다는 의미이다.
• 좌표는 x가 증가하는 순으로, x가 같다면 y가 증가하는 순으로 주어진다.
• N개의 선분을 모두 그렸을 때, 수직선 위에 그어진 선분 길이의 총합을 출력한다.
• 선분을 겹치게 그리는 것도 가능하다.

코드💻

# boj, 15922 : 아우으 우아으이야!!, python3
# 그리디 알고리즘
import sys

def solve(n, l):
    start = l[0][0]  
    end = l[0][1]  

    target = end - start  

    for i in range(1, n):  
        if l[i][0] <= end and l[i][1] <= end:  
            continue
            
        target += l[i][1] - l[i][0]  

        if l[i][0] < end:
            target -= (end - l[i][0]) 

        start = l[i][0]  
        end = l[i][1]  
    
    return target


N = int(sys.stdin.readline())
x_y_list = []

for i in range(N):
    x_y = list(map(int, sys.stdin.readline().split()))
    x_y_list.append(x_y)
    

print(solve(N, sorted(x_y_list)))

결과😎

출처 && 깃허브📝

boj
github