문제 분석

이 문제도 BOJ 1931, BOJ 11000와 비슷하다. 적은 수의 선분만을 사용해서 특정 범위에서 빈 공간 없이 이어지는 선분을 만드는 것이 목표이다.

Key idea

먼저 문제에서 월/일로 각 원소를 주는데, 이를 1~365로 변환하여 수직선상의 한 점을 표현 할 수 있도록 변환하였다(다른사람들은 월 * 100으로 간단하게 처리). 가능한 적은 수의 선분만을 사용해서 범위를 채워야 하기 때문에 이 문제는 앞에서부터 가장 멀리까지 이어지는 선분을 선택하면 해결할 수 있다. 그래서 내가 생각한 방법은 다음과 같다.

1. 시작 위치를 기준으로 정렬
2. 각 선분을 조사하면서 현재 위치보다 앞에서 시작하는 선분 중 종료지점이 가장 큰 선분을 선택하고 현재위치를 갱신
3. 현재위치가 범위의 끝을 넘어가면 종료

Solution

위의 아이디어대로 문제를 풀기 위해, 각 선분의 종료지점을 최대힙에 담아 관리했다. 모든 선분을 탐색하면서 시작지점이 현재 위치보다 앞에있는 선분은 힙에 추가하고, 현재 위치보다 뒤에서 시작하는 선분을 만나면 힙에서 종료지점이 가장 큰(가장 멀리까지 이어지는)것을 선택하여 선분을 연장한다.

import sys
import heapq

n = int(sys.stdin.readline())

month_start = [1, 32, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335]
schedules = []
for _ in range(n):
    sm, sd, em, ed = tuple(map(int, sys.stdin.readline().strip().split(' ')))
    s = month_start[sm-1] + (sd-1)
    e = month_start[em-1] + (ed-1)
    schedules.append((s, e))

schedules.sort(key=lambda x: (x[0], x[1]))
hq = []
now = 60

result = 0

for i in range(n):
    start, end = schedules[i]

    if start <= now:
        heapq.heappush(hq, -end)
    else:
        if len(hq) == 0:
            result = 0
            break
        else:
            now = -(heapq.heappop(hq))
            result += 1
            hq.clear()
            if start <= now:
                heapq.heappush(hq, -end)
            else:
                result = 0
                break

    if now > 334:
        break

if now <= 334 and len(hq) > 0:
    if -hq[0] > 334:
        result += 1
    else:
        result = 0

print(result)

여담으로 한참동안 같은 테스트케이스에서 막혔는데, 알고보니 문제를 잘못 이해해서 <를 <=로 계산하고 있었다. 앞으로는 꼭 문제를 꼼꼼하게 확인해야겠다.

그리고 다른 풀이를 보면서 배운건데, 파이썬에서 리스트에 대한 for문을 사용할 때 반복문 안에서 리스트의 원소를 지우면 정상적으로 동작하지 않는다. 그래서 리스트를 변형해야되는 경우 for보다는 while을 사용하면 의도한대로 동작하는 것 같다. 대신 while을 쓸 때는 무한루프에 빠지지 않도록 주의해야 한다.

• BOJ 2457 공주님의 정원