오늘의 회고

오늘은 그리디로 공주님의 정원 문제를 풀었다. 그리디는 뭔가 쉬운 것 같으면서도 풀이를 생각해내는 게 어려운 것 같다.

---

풀이

매번 현재 시점에서 피어있는 꽃 중에서 가장 마지막에 지는 꽃을 선택

처음에 3월 1일을 기준으로 그 전에 피고 가장 마지막에 지는 꽃을 갱신하면서 반복문을 돈다.
만약 for문을 통해 마지막에 지는 꽃으로 갱신이 안됐다면 return 0
for문 이후에는 지는 시간이 현재 시간으로 갱신되어 현재 시간이 12월 1일 되기 전까지 반복한다.

---

코드

import sys
input = sys.stdin.readline

n = int(input())
flowers = []

for _ in range(n):
    a, b, c, d = map(int, input().split())
    flowers.append([a*100+b, c*100+d]) # 1/1~5/30이면 [101, 530] 저장


def sol():
    current_time = 301
    answer = 0 # 선택한 꽃의 개수
    while current_time < 1201: # 1130까지 피어있어야함
        next_time = current_time # 이번에 추가할 꽃으로 인해 변경된 시간
        
        for i in range(n):
            if flowers[i][0] <= current_time and flowers[i][1] > next_time:
                next_time = flowers[i][1] # 지는 시간 갱신
        if next_time == current_time: # 현재 시간에서 전진 불가
            return 0
        answer += 1
        current_time = next_time # 지는 시간이 현재 시간이 됨
    return answer

print(sol())