[Python 3] BJ 2457-공주님의 정원

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

2457번: 공주님의 정원

어떻게 갓난아기인 공주의 취향을 알아냈는지는 의문이다.

회의실 배정 문제의 변형판. 단 그 문제와 다르게 마지막 꽃이 시들기 전에 피는 꽃 중 가장 늦게 지는 꽃을 고르면 된다.

다른 사람들은 100M+D 형태로 날짜를 저장했지만 힙스터 기질이 발동하여 그냥 경과일수로 저장하게 만들었다.

새로 꽃을 추가할 때마다 리턴 값+=1 하는 것보다 선택된 꽃의 배열을 만드는 것이 약간 더 빨리 결과가 나왔다.

import sys

accumulation={1:0, 2:31, 3:59, 4:90, 5:120, 6:151, 7:181, 8:212, 9:243, 10:273, 11:304, 12:334}
def md_to_d(month, day):
  return accumulation[month]+day
    
flowers=[]

N=int(sys.stdin.readline())

for i in range(N):
  start_month, start_day, end_month, end_day=map(int, sys.stdin.readline().split())
  flowers.append((md_to_d(start_month, start_day), md_to_d(end_month, end_day)))
selected=[]
start=0
end=60

startdate=60
enddate=334
flowers.sort(key=lambda x:(x[0], x[1]))


x=-1
temp=0
changed=0
selected=[]
while end<=enddate and x<N:
  changed=0
  x+=1
  for i in range(x, N):
    if flowers[i][0]>end:
      break
    if temp<flowers[i][1]:
      temp=flowers[i][1]
      x=i
      changed=1
  if changed==1:
    end=temp
    selected.append(flowers[x])
  else:
    selected=[]
    break
print(len(selected))