공주님의 정원[백준 2457]

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

 

배열 입력을 받고 순서대로 정렬한 후에 그리디 알고리즘으로 풀면 된다. 

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

for _ in range(n):
    flowers.append(list(map(int, input().split())))

# 날짜를 정수로 변환 (MMDD 형식으로 변환)
def date_to_int(month, day):
    return month * 100 + day

# 꽃의 피는 날과 지는 날을 MMDD 형식으로 변환하여 저장
flowers = [(date_to_int(start_month, start_day), date_to_int(end_month, end_day)) for start_month, start_day, end_month, end_day in flowers]

# 꽃을 피는 날짜 기준으로 오름차순, 같은 경우 지는 날짜 기준으로 오름차순 정렬
flowers.sort()

current_end = date_to_int(3, 1)  # 시작 날짜 (3월 1일)
target_end = date_to_int(11, 30)  # 종료 날짜 (11월 30일)
count = 0
i = 0
last_end = 0
while current_end <= target_end:
    found = False
    while i < n and flowers[i][0] <= current_end:
        last_end = max(last_end, flowers[i][1])
        i += 1
        found = True
    
    if not found:
        print(0)
        break
    
    current_end = last_end
    count += 1
else:
    print(count)