테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 공주님의 정원 ======

===== 풀이 =====
  * 그리디 알고리즘
  * 3월 1일에는 꽃이 피어있어야 한다. 즉, 피는날이 3월 1일 이전인 꽃들중에서 최소 한개는 선택을 해야 한다. 이때 선택하는 꽃은, 지는 날이 가장 늦은 꽃을 선택하는 것이 최적이다. 만약에 지는날이 가장 늦은 꽃조차, 3월 1일 이전에 진다면, 3월 1일에는 아무 꽃도 피어있을수 없으므로 0을 출력하고 종료. 그렇지 않고 지는날이 3월 1일 이후의 M월 D일 이라고 한다면, 이제 다시 피는 날이 M월 D일 이전인 꽃들 중에서 한개를 선택하고, 이것을 지는날이 11월 30이후인 꽃을 고르게 될때까지 반복하면 된다.
  * 알고리즘은 단순하지만, 구현이 조금 까다롭다. 처음에 피는 날 순서대로 꽃을 정렬해준 다음에, 정렬된 꽃 리스트를 순회하면서, 지금 심은 꽃이 지는 날짜, 다음에 심을 꽃의 후보, 현재까지 심은 꽃 갯수를 갱신해주면 되기는 한다. 
  * 시간복잡도는 정렬에 O(nlogn)이 걸리고, 순회하면서 처리하는 것은 O(n)이 걸리므로, 총 O(nlogn).

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 2457. 공주님의 정원".

- Problem link: https://www.acmicpc.net/problem/2457
- Solution link: http://www.teferi.net/ps/problems/boj/2457

Tags: [Greedy]
"""

import sys

FIRST = (3, 1)
LAST = (11, 30)


def main():
    N = int(sys.stdin.readline())
    flowers = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    flowers.sort()
    next_target = target = FIRST
    flower_count = 0
    for m1, d1, m2, d2 in flowers:
        if (m1, d1) > next_target:
            print('0')
            break
        elif (m1, d1) > target:
            target = next_target
            flower_count += 1
        next_target = max(next_target, (m2, d2))
        if next_target > LAST:
            print(flower_count + 1)
            break
    else:
        print('0')


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_4}}