[백준/Python]2457: 공주님의 정원

문제

https://www.acmicpc.net/problem/2457
백준 문제집 - 0x11강 - 그리디

 

알고리즘: 그리디, 정렬

---

풀이

총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. (올해는 4, 6, 9, 11월은 30일까지 있고, 1, 3, 5, 7, 8, 10, 12월은 31일까지 있으며, 2월은 28일까지만 있다.)

이러한 N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다.
1. 공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.
2. 정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다.

N개의 꽃들 중에서 위의 두 조건을 만족하는, 즉 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오.

입력값은 (피는 월, 피는 일, 지는 월, 지는 일)형태로 주어진다.
3월 1일부터 11월 30일까지 꽃이 매일 최소 한가지는 피어있도록 선택해야한다.
주의해야 할 점은 지는 날짜가 5월 10일이면 실제론 5월 9일날까지만 피어있다는 뜻이므로 마지막 꽃이 지는 날짜는 최소 12월 1일이어야한다.

 

사실 딕셔너리로 열심히 뚜들겨보다 막혀서 풀이를 찾아봤다...
대부분은 (피는 월 * 100) + 피는 일, (지는 월 * 100) + 지는 일로 변형해서 풀던데 굳이 그렇게 할 필요는 없을것같다.

 

먼저 입력값들을 오름차순으로 정렬해준다. (우선순위와 인자 순서가 같기때문에 key값은 따로 필요없다.)
그러면 꽃이 빨리 피고 지는 순으로 정렬되는데, 차례대로 탐색을 시작한다.

꽃이 하루도 빠짐없이 피어있게 하려면 어떻게 해야할까?
마지막 꽃이 지는 날짜를 기준으로 새로 심는 꽃의 피는날이 빠르거나 같고, 지는날은 느려야한다.
왜 같은 경우도 따져야하냐면 실질적으로 꽃이 피어있는 기간은 (지는날 - 1)이기 때문이다.
예를들어 마지막 꽃의 지는날이 (4, 7)이고, 새로운 꽃의 피는날이 (4, 8)이라면 4월 7일에는 아무런 꽃도 존재하지 않는다.
따라서 1) 마지막 꽃이 지는날짜, 2) 마지막 꽃의 인덱스번호, 3) 선택한 꽃의 갯수 를 저장해가며 탐색해야한다.
문제 조건을 보면 3월 1일부터 꽃이 피어있어야 하므로 (1)의 초기값을 (3, 1)로 저장 후 시작한다.

 

꽃을 정렬된 순서대로 탐색하며 위 조건 새로운 꽃이 피는날 <= (m, d) < 새로운 꽃이 지는날을 만족한다면 "심을 수 있는 꽃 중 가장 효율적인 꽃"을 탐색한다.
즉, 조건을 만족하는 꽃 중 가장 늦게 지는 꽃을 찾는것이다.
매 꽃마다 아래의 조건을 확인 후 가장 늦게 지는 날 latest를 업데이트한다.
조건을 만족하면서 latest보다 지는 날짜가 늦다면 latest를 업데이트해주고, 꽃이 피는 날짜가 (m, d)보다 늦다면 더 이상의 탐색은 무의미하므로 종료한다.

더 이상 만족하는 꽃이 없다면 마지막 꽃이 지는날을 latest로 업데이트 후 latest의 다음 꽃부터 다시 탐색을 시작한다.

탐색 중 마지막 꽃이 지는날이 11월 30일보다 커지면 탐색 종료 후 지금까지 선택한 꽃의 갯수를 출력한다.
만약 모든 꽃을 체크했음에도 (3월 1일 ~ 11월 30)을 만족할 수 없다면 0을 출력한다.

참고로 Python은 while~else도 사용할 수 있는데, while문을 break없이 마쳤다면 else문이 실행되는 구조다. 아주 좋다...

 

전체 코드

# 메모리: 41384KB / 시간: 224ms
from sys import stdin


input = stdin.readline

N = int(input())
flowers = sorted(tuple(map(int, input().split())) for _ in range(N))
ret = 0

# 꽃이 지는 날짜 (초기값: 3월 1일)
end = (3, 1)
i = 0

while i < N:
    m1, d1, m2, d2 = flowers[i]
    latest = 0

    # 현재 꽃이 피는날 <= end < 지는날이면 현재 꽃을 심을 수 있음.
    if (m1, d1) <= end < (m2, d2):
        latest = (m2, d2)

        # 위 조건하에 가장 늦게 지는 꽃을 찾기
        while i < N-1:
            m1, d1, m2, d2 = flowers[i+1]
            if (m1, d1) > end:  # 꽃이 피는날짜가 end보다 늦다면 탐색 종료
                break
            if (m2, d2) > latest:
                latest = (m2, d2)
            i += 1

        end = latest
        ret += 1

        # 꽃이 지는 날짜가 11월 30일보다 늦다면 출력 후 종료. (실제 꽃이 지는날은 (지는날 - 1)이기 때문에 같거나 작으면 안됨.)
        if latest > (11, 30):
            print(ret)
            break
    i += 1
else:
    # break없이 빠져나올경우 (꽃이 지는 날짜가 11월 30일을 못넘길경우)
    print(0)