백준 2170 (선 긋기)

백준 2170 (선 긋기)

문제 링크

문제 링크 : https://www.acmicpc.net/problem/2170

문제 접근

어떤 도화지에 시작점과 끝점을 연결해서 n개의 선분을 긋습니다. 각 선분은 서로 겹쳐서 그릴 수 있습니다. 즉, 겹치는 부분은 하나의 선분으로 취급해도 됩니다. 총 선분의 길이를 구하는 문제입니다. 만약 현재까지 만든 선분들에 대해 겹치는 선분이 존재한다면, 하나의 선분으로 합치면 될 듯 합니다. 하지만 그렇지 않은 경우라면? 일단 저장을 한 후, 나머지 무작위로 주어진 입력에 대해 검사를 해보면 되겠죠. 하지만 이러한 방법은 최악의 경우, 즉 n개의 모든 선분들이 겹치지 않는다면 총 n개의 선분을 저장하고, 저장된 선분에 대해서 하나하나 검사를 해야 합니다. 이 경우 시간 복잡도는 O(N^2)이 되겠죠. 너무 비효율적인 풀이입니다.

어쨌거나, 선분에 대해서 합치는 작업은 무조건 해야 하긴 하는데, 이를 효율적으로 해보고 싶습니다. 어떻게 해야 할까요?

어떤 선분을 기준으로, 입력 선분이 겹칠 수 있다면 겹치는 작업은 오래 걸리지 않습니다. 입력이 과거 시점(저장되어 있는 선분)을 고려하지 않고, 현재에 집중한다면 O(n)의 시간으로 풀 수 있습니다. 하지만 입력은 무작위로 주어진다는 것이 문제인 것이죠.

그렇다면 입력을 최대한 좋게 전처리를 해봅시다. 시작 점을 기준으로 정렬을 했습니다. 그렇다면 다음 입력은 어쨌거나, 지금 선분보다 시작점이 무조건 뒤에 있음이 보장됩니다. 합칠 수 있다면 현재 선분과, 다음 입력 선분(미래 선분이라고 설명하면 이상하긴 한데 그렇게 불러도 될 것 같습니다)을 합치자는 것입니다. 만약 합쳐지지 않는다면 앞으로의 선분들도(먼 미래의 선분들도), 절대 현재 선분과 겹쳐지지 않음이 보장됩니다. 이를테면, 아래 그림과 같이 그릴 수 있겠네요.

요약하자면, 시작 점을 기준으로 정렬 후(끝 점은 관계 없습니다), 다음 선분이 겹쳐진다면 겹치고, 겹쳐지지 않는다면 총 선분의 길이를 구하는 것이니 기존 선분의 길이는 정답에 추가할 수 있도록 저장을 해두고, 선분을 새로 갱신하면 됩니다.

소스 코드

import sys

n=(int)(input())
lines=[]
for _ in range(n) :
    s,e = map(int ,sys.stdin.readline().split())
    lines.append((s,e))

lines.sort() #시작 기준으로 정렬
start=0
end=0
line_save=[]
for line in lines :
    if start==0 and end==0 :
        start = line[0]
        end=line[1]
    else : #맨 처음이 아니라면 
        new_line_start=line[0]
        new_line_end=line[1]
        if end>=new_line_start : #현재 선분의 끝점보다 입력 선분의 시작점이 작다면 
            if new_line_end >end : #만약 입력 선분의 끝점이 현재 선분의 끝점보다 크다면 합쳐줌.
                end=new_line_end 
            else : #입력 선분의 끝점이 현재 선분의 끝점보다 작거나 같으면 현재 선분이 더 크므로 고려할 필요x 
                pass
        else :
            line_save.append(end-start)
            start = new_line_start
            end= new_line_end
            
line_save.append(end-start)
print(sum(line_save))

아래 코드에서 else 부분은 빼도 됩니다. 저는 빼고 코드를 작성했고, 이해를 위하여 위 코드에 추가하였습니다.

if new_line_end >end : #만약 입력 선분의 끝점이 현재 선분의 끝점보다 크다면 합쳐줌.
    end=new_line_end 
else : #입력 선분의 끝점이 현재 선분의 끝점보다 작거나 같으면 현재 선분이 더 크므로 고려할 필요x 
    pass

마무리하며

1) 탐욕적인 문제입니다. 이와 흐름이 유사한 1931(회의실 배정), 20440(모기) 문제가 생각납니다. 다음 포스팅은 아마 20440을 하지 않을까 싶습니다.

2) 벌써 1월도 1/3이 지나가고 있네요. 시간이 빠름을 매번 느낍니다. 벌써 25살입니다.
개인 블로그에 “벌써 23년”이라고 적힌 소개글을 24년이라고 수정을 했습니다.
왼쪽 사이드바의 하단 버튼 5개 중 가운데 버튼을 누르면 블로그로 이동합니다.
아무튼 각설하고, 2022->2023도 진짜 빠르게 느껴졌는데, 2023->2024는 더 빠르게 느껴집니다.
졸업까지 얼마 남지 않았습니다. 열심히 잘 살아야겠습니다.