[python] 백준 2457 공주님의 정원

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

2457번: 공주님의 정원

 

문제해결

• 월/일 을 표현할때 '월*100+일'로 표현하여 비교할 수 있다.
• 투포인터를 이용해 문제를 해결할 수 있다.
• 3월 1일~11월 30일 꽃이 매일 한 개 이상 피어있어야 하므로 301~1130을 포함하는 범위를 만들면 된다.
• start = 301, end = 0으로 시작하여 start범위이하부터 시작하여 지는 범위가 1130 보다 커지면 가능한 경우가 있고 그렇지 않으면 없는 것이다.

 

CODE

import heapq
n = int(input())
memo = []
for _ in range(n):
    a, b, c, d = map(int, input().split())
    a *= 100
    c *= 100
    memo.append([a+b, c+d])
memo.sort(key=lambda x:(x[0], x[1]))
cnt = 0
end = 0
start = 301

while memo:
    if start >1130 or start < memo[0][0]: break

    for _ in range(len(memo)):
        if start >= memo[0][0]:
            if end <= memo[0][1]:
                end = memo[0][1]
            memo.remove(memo[0])
        else:
            break
    start = end
    cnt += 1
if start <= 1130:
    print(0)
else:
    print(cnt)