[BOJ 2457, Python 3] 공주님의 정원

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

2457번: 공주님의 정원

 

 

풀이

회의실 배정 문제랑 비슷한데, 날짜 처리도 그렇고 꽃이 지기 전에 꽃을 미리 구해놔야해서 생각하기가 좀 까다로웠던 문제였습니다.

 

일단 값을 받을 때 날짜를 1월 1일이면 101, 12월 31일이면 1231처럼 월에 100을 곱해줘서 일이랑 더해줍니다. 다 했으면 이제 날짜순으로 오름차순 정렬을 해주면 됩니다.

그리고 먼저 3월 1일 이전에 꽃이 피면서 제일 늦게 지는 꽃을 구합니다.(꽃이 지는 날을 e라고 합시다.)

그 후부터는 for문을 이용해 꽃이 피는 날이 e 이전이면서 꽃이 가장 늦게 지는 꽃을 찾아서 업데이트 해줍니다.

배열을 오름차순으로 정렬했으므로 e를 업데이트 했으면 이전에 봤던 꽃은 볼 필요가 없으니 한 번도 확인하지 않은 제일 작은 인덱스부터 꽃이 피는 날이 e 이전이면서 꽃이 가장 늦게 지는 꽃을 찾아서 e의 값이 1130이상이 될 때까지 업데이트를 반복하면 됩니다.

 

0을 출력하는 것은 꽃이 지는 날이 e보다 클 경우입니다. 날짜순으로 오름차순 정렬했으니 꽃이 피는 날이 e보다 크면 나머지 꽃들도 전부 e보다 크다는 것이 보장되어 있습니다.

 

 

코드

input = __import__('sys').stdin.readline
n = int(input())
arr = []
for i in range(n):
    a, b, c, d = map(int, input().split())
    if 100*c+d < 301 or 100*a+b > 1130: continue
    arr.append([100*a+b, 100*c+d])
arr.sort()
flower = [-1, -1]
idx = -1
for i in range(n):
    if arr[i][0] > 301: break
    if arr[i][1] > flower[1]:
        flower = arr[i]
        idx = i
ans = 1
day = flower[1]
while day <= 1130:
    next_flower = [-1, -1]
    for i in range(idx, n):
        if arr[i][0] > day: break
        if flower[0] < arr[i][0] <= flower[1] < arr[i][1]:
            if arr[i][1] > next_flower[1]:
                next_flower = arr[i]
                idx = i
    if next_flower[0] == -1:
        print(0)
        exit()
    flower = next_flower
    day = flower[1]
    ans += 1
print(ans)