[Python] 백준 2457번: 공주님의 정원

최소의 꽃들만 선택해서 3월 1일부터 11월 30일까지 매일 꽃이 피어 있도록 해야 하는 문제입니다.

가장 최근에 심은 꽃이 latest_date 날에 진다고 가정했을 때,
현재의 꽃에 대해 피는 날짜 <= latest_date < 지는 날짜 이 성립한다면
이전에 심은 꽃과 현재의 꽃을 함께 선택할 수 있습니다.

하지만 문제에서는 최소의 꽃들만 선택해야하기 때문에,

1. 피는날 -> 지는날 기준으로 오름차순 정렬

   (1, 1) (5, 31)
   (1, 1) (6, 30)
   (5, 15) (8, 31)
   (6, 10) (12, 10)

2. 현재의 i번째 꽃을 이전에 심은 꽃과 함께 선택할 수 있다면,
   latest_date < 피는 날짜 가 될 때까지 다음 순번의 꽃을 계속 확인하며
   가장 마지막에 지는 꽃을 찾아 심기

   latest_date가 3월 1일이고, i = 0이라면
   (3, 1) >= (1, 1) 에서 i=0
   (3, 1) >= (1, 1) 에서 i=1
   (3, 1) < (5, 15) 에서 i=2는 미포함

   에서 i=0, 1중 가장 마지막에 지는 꽃인 i=1을 선택하여 심습니다.
   이후 i = 2부터 다시 반복

3. 11월 30일까지 모두 심었다면 종료

   latest_date > (11, 30)

   이때 latest_date는 가장 최근에 심은 꽃이 지는 날짜이므로,
   latest_date = (11, 30) 이라면 11월 30일에는 가장 최근에 심은 꽃이 이미 져버린 상태라는 점에 유의해야 합니다.

저는 날짜를 (월, 일)과 같이 tuple로 표현했습니다.
따라서 피는 날짜는 (sm, sd), 지는 날짜는 (em, ed)로 표현했습니다.

n = int(input())
f = [list(map(int, input().split())) for _ in range(n)]
f.sort()

i = 0
result = 0
latest_end = (3, 1) # 3월 1일부터 체킹

while i < n:
    sm, sd, em, ed = f[i]
    if (sm, sd) <= latest_end < (em, ed):
        max_end = (em, ed) # 현재 심을 수 있는 꽃들 중 가장 마지막에 지는 꽃 찾기 시작
        while i < n-1: 
            nsm, nsd, nem, ned = f[i+1]
            if latest_end < (nsm, nsd): # 현재 심을 수 있는 꽃이 i번째까지라면 종료
                break
            if max_end < (nem, ned):
                max_end = (nem, ned)
            i += 1
            
        # 찾은 꽃 심기
        result += 1
        latest_end = max_end
        
        # 11월 30일까지 모두 심었다면 종료
        if (11, 30) < latest_end:
            print(result)
            exit(0)
    i += 1

print(0)

현재 심을 수 있는 꽃들 중 가장 마지막에 지는 꽃을 심는다는 점과
피는 날짜를 기준으로 오름차순 정렬하여 현재 심을 수 있는 꽃인지 아닌지를 그리디하게 판별한다는 점에서 그리디 알고리즘임을 알 수 있습니다.