[2457] 공주님의 정원

문제

https://www.acmicpc.net/problem/2457

풀이

꽃의 피는 날이 빠른 순으로 정렬을 해줍니다.

꽃이 피는 날이 넘으면 안되는 한계선을 담을 left 변수와, 현재 꽃이 마지막으로 지는 날짜를 담을 right 변수를 만들어 줍니다. 처음엔 3월 1일로 초기화 해줬습니다. 꽃이 피는 날은 3월 1일보다 빠르거나 같아야하고, 펴있는 꽃이 없기 때문입니다.

이제 정렬된 순서대로 꽃을 선택해 주면됩니다.

현재 꽃이 피는 날짜가 left보다 작다면 선택할 수 있는 꽃이라 볼 수 있습니다. 이제 고려해야하는 것은 지는 날짜입니다. 일단 최대한 적은 수의 꽃을 유지하기 위해서는 지는 날짜가 더 늦는 꽃을 선택해야합니다. 따라서 현재 꽃의 지는 날과 right를 비교해서 더 늦는 꽃을 선택해줍니다. 물론 right도 해당 꽃이 지는 날로 재갱신 해줍니다.

이번엔 현재 꽃이 피는 날짜가 left보다 늦고, right보다 꽃의 피는 날짜가 빠르거나 같다면 현재 선택되어 있는 꽃은 어쩔 수 없이 선택이 되어야한다는 의미이고 현재 선택 대기 중인 꽃이 피는 날이 right보다 빠르거나 같다는 의미는 끊기지 않고 더 이어갈 수 있다는 의미이므로 꽃의 수를 카운트 해주고 left와 right를 새로 갱신해주면 되는데 right의 경우는 가장 긴 값을 선택해주면 됩니다.

import sys
from collections import deque

N = int(sys.stdin.readline())
flowers = [tuple(map(int, sys.stdin.readline().strip().split())) for _ in range(N)]
flowers.sort()
queue = deque()
left = right = (3, 1)
max_right = (11, 30)
result = 0

# d1 = (월, 일)
def compare(d1, d2):  # d1 < d2 return 1, d1 == d2 return 0, d1 > d2 return -1
    if d1 == d2:
        return 0
    if d1[0] < d2[0] or (d1[0] == d2[0] and d1[1] < d2[1]):
        return 1
    return -1

for flower in flowers:
    m_1, d_1, m_2, d_2 = flower
    if compare(left, (m_1, d_1)) != 1:
        if compare(right, (m_2, d_2)) == 1:
            right = (m_2, d_2)
    elif compare(right, (m_1, d_1)) != 1:
        result += 1
        left = right
        if compare(right, (m_2, d_2)) == 1:
            right = (m_2, d_2)
		else:
				break

    if compare(max_right, right) == 1: # 이미 11월 30을 넘어섰다면 종료
        result += 1
        break
if compare(max_right, right) == 1:
    print(result)
else:
    print(0)