[백준-파이썬] 2024: 선분 덮기

문제 풀러 가기!

재미있는.. 그리디 문제였다.. ^^

일단 입력을 받는다. 0, 0 이 나올 때까지 받으니까 while을 이용했다. 혹시 몰라서 출발점과 끝점이 같으면 받지 않았고, 출발점이 음수이고 끝나는 점이 0 이하이면 받지 않았다. 

그리고 정렬~ 출발점 빠른 순 -> 출발점이 같으면 끝나는 점이 빠른 순으로 정렬했다.

그 후에 그 상황에서 끝나는 점의 좌표(finish_idx)와 사용한 선의 개수를 0으로 초기화했다.

그리고 쭉~~ 봤다.  그러면서 finish_idx보다 일찍 시작하는 선분을 후보에 넣었다. 그리고 그 중에 끝나는 좌표가 제일 큰 선분을 사용하는 게 이득이니까! 제을 큰 끝나는 좌표를 finish_idx에 대입하고, 사용한 선의 개수를 1 더했다. 만약에 finish_idx가 M과 같거나 크면, 0부터 M까지 쭉~ 이어졌다는 뜻이니까 그때까지 사용한 선의 개수를 리턴했다. 그게 바로 답이 된다 ~ 

아! 남은 선분들 중에서 finish_idx보다 일찍 시작하는 선분이 없다면.. 선분이 M까지 이어지지 않는 것이니까 바로 0을 리턴했다. 

 

import collections
import sys

input = sys.stdin.readline

M = int(input())

# 입력 받기
lines = []
while True:
    start, end = map(int, input().split())
    # 입력 끝
    if start == 0 and end == 0:
        break

    if start == end:  # 출발, 끝점 같으면 필요 X
        continue

    if start < 0 and end <= 0:  # 출발점이 음수이고, 끝나는 점이 0 이하이면 필요 X
        continue

    lines.append((start, end))

sorted_lines = collections.deque(sorted(lines))  # 정렬(출발점 빠른 순 -> 출발점 같으면, 끝나는 점 빠른 순)


def sol():
    finish_idx = 0  # 지금 상황에서 끝나는 점
    use_line_cnt = 0  # 사용한 선의 개수

    while sorted_lines:  # 쯕~ 보자!
        candidates = []  # 지금 쓸 수 있는 후보

        # 일단 하나를 꺼냄
        now_line = sorted_lines.popleft()
        if now_line[0] <= finish_idx:  # 전에 꺼가 끝나는 것보다 일찍 시작하면
            candidates.append(now_line[1])  # 후보에 넣기

        if finish_idx < now_line[0]:  # 가장 빨리 시작하는 선분이 이전 선분이 끝나는 좌표보다 나중에 시작하면
            # 선 덮는 방법 존재하지 않음
            return 0

        # 후보들(지금 선분 끝나는 것보다 일찍 시작하는 점들)
        while sorted_lines:
            tmp = sorted_lines.popleft()

            if tmp[0] <= finish_idx:  # 이전 것이 끝나는 것보다 일찍 시작
                candidates.append(tmp[1])  # 후보에 넣기

            else:  # 아니면
                sorted_lines.appendleft(tmp)
                break  # 이제 후에 나올 아이들은 시작점이 더 나중이니까, 더 이상 후보 나올 수 없으니 break

        finish_idx = max(candidates)  # 끝나는 시점 업데이트 (지금 선분 끝나는 것보다 일찍 시작하는 점들 중에, 젤 늦게 끝나는 것)
        use_line_cnt += 1  # 선분 하나 사용했으니 1 추가

        if finish_idx >= M:  # M까지 왔으면
            return use_line_cnt

    return 0


print(sol())