[Solved] BOJ: 2457 | 공주님의 정원

오랜만에 백준 풀이>,<...
정렬 기반 빡구현 문제였다! 근데 문제 조건 잘 체크해야 함...
난 부등호때문에 엄청 고생했다ㅠ.ㅠ

문제

3월 1일부터 11월 30일까지 매일 최소 1개 이상의 꽃이 피어있는 상태를 유지하도록 할 떄,
꽃의 개수를 최소화하기

입력

첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, 3 8 7 31은 꽃이 3월 8일에 피어서 7월 31일에 진다는 것을 나타낸다.

주의

지는 날짜를 유의해야한다!! 지는 날짜 이전까지 꽃이 피어있는 것으로 친다.
ex) 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다.

문제 접근

• 흔한 회의실 문제와 비슷하게 생각했다.
  일단 정렬은 해야겠지? 기본 of 기본 꽃을 최대화하든 최소화하든 일단 기준이 있어야하기 때문에...

• 월 별 날짜 개수가 다르기 때문에 그냥... 편하게 1년을 365일로 계산하기로 했다.

  MONTH = {1:31, 2:28, 3:31, 4:30, 5:31, 6:30, 7:31, 8:31, 9:30, 10:31, 11:30, 12:31}
  START = 60   # 3월 1일
  END = 334   # 11월 30일

• 항상 꽃이 피어있는 상태를 유지해야하기 때문에 꽃과 꽃을 이어가는 것이 중요하다.

문제 풀이

• 꽃의 개수를 최소화하는 것이 목적이기 때문에, 꽃이 피어있는 기간이 길수록 좋다!
  그래서 개화시기가 이르면서 꽃이 피어있는 기간이 긴 순서로 정렬했다.

# open이 빠르고 close가 느린 순서로 정렬
flowers = sorted(flowers, key=lambda x:x[1], reverse=True)
flowers = sorted(flowers, key=lambda x:x[0])

• 현재 기준에서 다음 기간으로 이어갈 수 있는 꽃인지 체크해야한다.
  예를 들어 현재 기준이 3월 1일이라면, 적어도 3월 1일부터 개화하거나 그 이전부터 개화하는 꽃들만 다음 기간을 이어갈 후보가 될 수 있다.

"""
1 cur_start ------------------------------------ cur_end
2             cur_start --------------------------------------- cur_end
3                            cur_start ------------------------------------ cur_end
4                                                                                          cur_start ------ cur_end
"""

1의 다음 기간을 이어갈 꽃의 후보는 2, 3이다.
4는 기간을 이어갈 수 없기 때문에 불가하다.

"""
1 cur_start ----------- cur_end
2 cur_start ---------------------- cur_end
3 cur_start ------------------------------------ cur_end
4             cur_start --------------------------------------- cur_end
5                            cur_start ------------------------------------ cur_end
6                                              cur_start ----------------------------------- cur_end
7                                                             cur_start ------- cur_end
"""

후보들 중에서 최대한 꽃이 지는 시기가 느린 것으로 계속 갱신해준다.
위의 예시를 기준으로,
현재 기준이 1, 2, 3에 해당하는 cur_start라면, 꽃이 지는 시기가 가장 느린 것은 3번이 된다.

for flower in flowers:
    # print(flower)
    if flower[0] <= cur_start:
        cur_end = max(cur_end, flower[1])

만약 현재 기준에 들어맞지 않는(다음 기간을 이어갈 수 없는) 꽃이 등장했다면,
현재 기준에 들어맞았던 기간 중, 가장 늦게 꽃이 지는 날짜를 현재 기준으로 갱신해준다.
그리고 그 다음 다시 계속 반복함.

    else:
        cur_start = cur_end   # 새로운 현재 기준 갱신
        if flower[0] <= cur_start:
            cnt += 1
            cur_end = max(cur_end, flower[1])

위의 예시를 기준으로 보면 4번째 꽃은 기존의 cur_start와 동시에 또는 먼저 개화하지 않아서 현재 기준을 이어갈 수 없는 꽃이다.
따라서 이전까지 등장했던 꽃이 가장 늦게 지는 cur_end 값을 cur_start값으로 새로 갱신해준다.
그럼 3번 꽃의 cur_end값이 4번째 줄부터의 현재 기준이 되는 시작 값이 된다.
3번째 꽃의 cur_end보다 먼저 개화하는 4, 5 6번째 꽃이 기준에 들어맞는 꽃이며,
이 중 꽃이 지는 날짜가 제일 나중인 5번째 꽃의 꽃 지는 날짜가 그 다음 cur_start가 된다.
마주한 꽃이 지는 시기가 11월 30일을 넘어간다면, 체크해야할 조건은 만족하므로 for문을 멈춘다.

    if cur_end > END:
        cnt += 1
        break

전체 코드

import sys
input = sys.stdin.readline

MONTH = {1:31, 2:28, 3:31, 4:30, 5:31, 6:30, 7:31, 8:31, 9:30, 10:31, 11:30, 12:31}
START = 60
END = 334

N = int(input())
flowers = []
for _ in range(N):
    open_month, open_day, close_month, close_day = map(int, input().split())

    open, close = 0, 0
    if open_month > 1:
        for i in range(1, open_month):
            open += MONTH[i]
    open += open_day

    if close_month > 1:
        for i in range(1, close_month):
            close += MONTH[i]
    close += close_day

    if open <= END and close > START:   # 3월 1일, 11월 30일에 걸쳐지거나 포함되는 flower인지 체크
        flowers.append((open, close))

# open이 빠르고 close가 느린 순서로 정렬
flowers = sorted(flowers, key=lambda x:x[1], reverse=True)
flowers = sorted(flowers, key=lambda x:x[0])
# print(flowers)

cnt = 0
cur_start = START
cur_end = START
for flower in flowers:
    # print(flower)
    if flower[0] <= cur_start:
        cur_end = max(cur_end, flower[1])
        # print(f'end changed: {cur_end}')
    else:
        cur_start = cur_end
        # print(f'start changed: {cur_start}')
        if flower[0] <= cur_start:
            cnt += 1
            cur_end = max(cur_end, flower[1])
            # print(f'end changed: {cur_end}')
    if cur_end > END:
        cnt += 1
        break

if flowers[0][0] > START:
    print(0)
else:
    if cur_end > END:
        print(cnt)
    else:
        print(0)