백준 2457 공주님의 정원

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

N개의 꽃이 주어지며, 각 꽃에 대해 피는 날짜와 지는 날짜가 주어진다.

심는 꽃의 수를 최소한으로 3월 1일부터 11월 30일까지 매일 한 가지 이상의 꽃이 피어 있도록 선택하는 경우 그 개수를 출력하는 문제이다.

월마다 며칠까지 있는지는 중요하지 않고, 조심해야 할 부분은 꽃이 지는 날짜 당일에는 꽃이 이미 져서 못 보는 것으로 친다는 부분이다.

예를 들어 꽃이 3 1 11 30으로 주어지는 경우, 3월 1일은 통과지만 11월 30일은 포함이 되지 않는다.

문제의 핵심은 최소한의 꽃으로 3월 1일부터 11월 30일까지 비는 날짜 없이 연결해야 하는 것이다.

빈 곳이 없도록 하기 위해 꽃들을 시작 날짜 오름차순 정렬하고 시작 날짜인 3/1일부터, 시작 날짜를 포함하는 모든 꽃들 중 지는 날이 가장 나중인 꽃을 선택하는 것을 반복하기로 하였다.

위 그림들처럼 현재 시작날짜보다 피는 날짜가 빠른 꽃들 중 지는 날짜가 가장 나중인 꽃들을 그리디하게 선택해서 풀 려고 생각을 하였다.

따라서 풀이 아이디어는 아래와 같이 구상하였다.

• 꽃들을 시작 날짜 기준 오름차순으로 정렬한다.
  (피는 날짜 같을 경우 지는 날짜 내림차순으로 정렬 - 그리디 보장 위함)
• 지는 날짜가 가장 긴 꽃을 뽑기 위한 PriorityQueue를 선언한다.
• 시작일을 3월 1일로 설정한다.
• 정렬된 각 꽃들에 대해, 피는 날짜가 현재 날짜거나 이전인 경우 PQ에 지는 날짜를 넣는다.
• 현재 날짜 이후라면, PQ에서 가장 긴 지는 날짜를 가져와 현재 날짜에 넣는다. 이후 현재 꽃도 큐에 넣는다.
  (여기서, 큐가 비었는데 뽑으려하거나 PQ에서 뽑아온 지는 날짜가 현재 꽃의 피는 날짜 이전이면 연결이 끊긴 것이므로 0 출력 후 종료)
• 모든 꽃을 순회했는데도 현재 날짜가 12월 1일 이전이라면 PQ에서 원소를 하나 꺼내 12월 1일까지 커버되나 보고 정답을 판단한다.

import java.util.*

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    val days = List(N){
        val (sm, sd, em, ed) = readLine().split(' ').map{it.toInt()}
        Pair(Date(sm, sd), Date(em, ed))
    }.sortedWith{ d1, d2 ->
        // 피는 날짜 오름차순, 피는 날짜 같으면 지는 날짜 내림차순 정렬
        when{
            d1.first.month != d2.first.month -> d1.first.month - d2.first.month
            d1.first.month == d2.first.month && d1.first.day == d2.first.day -> {
                if(d2.second.month == d1.second.month) d2.second.day - d1.second.day
                else d2.second.month - d1.second.month
            }
            else -> d1.first.day - d2.first.day
        }
    }

    var curStart = Date(3, 1)
    val endDate = Date(12, 1)

    var answer = 0
    
    // 가장 긴 지는 날짜 가져올 PQ
    val endDatePQ = PriorityQueue<Date>{ d1, d2 ->
        if(d1.month == d2.month) d2.day - d1.day
        else d2.month - d1.month
    }

    for(day in days){
        // 현재 날짜 or 이전인 경우, 지는 날짜를 PQ에 넣음
        if(isSameOrPast(curStart, day.first))
            endDatePQ.offer(day.second)
        else{
            // 3/1부터 연결되지 않은 경우
            if(endDatePQ.isEmpty()){
                print(0)
                return@with
            }

            // 가장 긴 지는 날짜의 꽃을 선택해, 현재 날짜를 지는 날짜로 
            val recent = endDatePQ.poll()
            curStart = recent

            // 가장 긴 지는 날짜 꽃을 가져왔는데, 현재 꽃이 피기 전에 지는 경우
            if(isPast(day.first, recent)){
                print(0)
                return@with
            }

            answer++
            endDatePQ.offer(day.second)
        }

        if(isSameOrPast(curStart, endDate))
            break
    }

    // for 문에서 break 되지 않고 마지막 한번 처리하지 못한 케이스 처리
    if(isPast(endDate, curStart)){
        // 현재 큐에서 가장 늦게 지는 꽃
        val recent = endDatePQ.poll()
        curStart = recent
        answer++

        // 가장 늦게 지는 꽃을 선택했는데도 12월1일 이전이면
        if(isPast(endDate, curStart))
            answer = 0
    }

   print(answer)
}

fun isSameOrPast(st: Date, en: Date) =
    if(st.month == en.month) en.day <= st.day else en.month <= st.month

fun isPast(st: Date, en: Date) =
    if(st.month == en.month) en.day < st.day else en.month < st.month

data class Date(
    val month: Int,
    val day: Int
)