[백준] 공주님의 정원

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

2457번: 공주님의 정원

그리디 문제입니다. 먼저, 각각의 꽃이 피고 지는 월, 일을 날짜로 변환하여 저장한 다음 꽃이 지는 날을 기준으로 정렬을 해줍니다. 그 다음 현재 꽃이 이전 꽃이 피기 전에 필 수 있으면 리스트에 추가해줍니다. 그 다음 기존에 선택된 꽃들을 체크하면서 현재 꽃이 포함할 수 있는 범위에 있는 꽃들은 필요가 없으므로 리스트에서 제거해주면 됩니다. 

 

import sys
INT_MAX = sys.maxsize

#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n = int(input())

month = [0] + [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
prefix = [0] * 13

# 각 월까지의 날짜합을 미리 저장해둔다.
for i in range(1, 13):
    prefix[i] += (prefix[i - 1] + month[i])

flower = []
for _ in range(n):
    m1, d1, m2, d2 = tuple(map(int, input().split()))
    f_start = prefix[m1 - 1] + d1
    f_end = prefix[m2 - 1] + d2

    # 꽃이 시드는 날짜가 더 뒤에 있는 꽃들만 저장
    if f_end > f_start:
        flower.append((f_start, f_end))
# 1월 1일 ~ 3월 1일까지를 미리 저장해둔다.
selected = [(1, prefix[2] + 1)]
# 11월 30일
target = prefix[10] + 30

# 끝나는 날짜를 기준으로 오름차순 정렬
flower.sort(key=lambda x: x[1])

for i, (start, end) in enumerate(flower):
    last = selected[-1]
    # 선택된 마지막으로 꽃이 지는 날짜보다 현재 꽃이 피는 날짜가 더 느리면 넘어간다.
    if last[1] < start:
        continue

    while len(selected) >= 2:
        prev_of_last = selected[-2]
        # 전전에 선택된 꽃이 피고 지는 범위에 닿을 수 있으면 이전 꽃은 필요가 없다
        if prev_of_last[1] >= start:
            selected.pop()
        else:
            break

    selected.append((start, end))


if len(selected) == 1:
    print(0)
else:
    cnt = 0
    flag = False
    for start, end in selected[1:]:
        cnt += 1
        if end > target:
            flag = True
            break
    # 11월 30일에 도달하여 break한 경우에만 답을 출력
    if flag:
        print(cnt)
    else:
        print(0)