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

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

2457번: 공주님의 정원

 

Difficulty : Gold 3

 

Status : Solved

 

Time : 00:46:24

 

---

 

문제 설명

 

오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다.

총 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개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다.

공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.
정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다. 
N개의 꽃들 중에서 위의 두 조건을 만족하는, 즉 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오. 

 

입력 및 출력

 

입력

 

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

 

출력

 

첫째 줄에 선택한 꽃들의 최소 개수를 출력한다. 만약 두 조건을 만족하는 꽃들을 선택할 수 없다면 0을 출력한다.

 

입력 예시

 

4
1 1 5 31
1 1 6 30
5 15 8 31
6 10 12 10

 

출력 예시

 

2

 

 

---

 

풀이

 

라인스위핑이라고 생각하고 풀이했으나... 최소 선분을 구해야 하므로 조금 머리가 꼬였다. 수많은 시행 착오와 맞왜틀 끝에 맞춘 문제. 사실 이 문제에 대한 더 깔끔한 답안이 존재할 수 있으리라 믿지만, 현재로써는 생각나지는 않는다.

 

우선, 꽃이 지는 날 당일부터 그 꽃이 더 이상 존재하지 않는다. 따라서 어떤 꽃이 존재하는 기간은 [시작일, 종료일-1]이 된다. 이 점을 염두해 두고 풀이해보자.

 

3월 1일부터 11월 30일까지의 구간 여부를 판별해야 하므로 우선 선분을 정렬한다. 이 때, 정렬 기준은 시작일 기준으로 오름차순, 종료일 기준으로 내림차순으로 진행하였다. 우리는 선분 구간을 저장하며, 다음 선분을 저장할지의 여부를 판단할 것이다.

 

• 마지막 선분 구간에 다음 선분이 포함될 경우 : 이 경우는 그 선분을 무시할 수 있다.
• 마지막 선분 구간과 다음 선분이 겹칠 경우 : 여기서 겹친다는 의미는 1. 위의 경우에 해당하지 않고 2. 앞선 선분의 끝점보다 뒤 선분의 시작점이 빠르거나 3. 앞선 선분의 끝점과 뒤 선분의 시작점의 차가 1일 경우에 해당한다. 이 경우는 직전의 선분 구간까지 고려하여 판별한다.
  • 직전의 선분 구간과 다음 선분이 겹치고, 마지막 선분 구간의 끝점보다 다음 선분의 끝점이 더 멀다면 마지막 선분 구간을 교체할 수 있다. 그리디하게, 같은 개수의 선분을 사용하며 더 넓은 기간을 포함시킬 수 있다.
  • 직전의 선분 구간과 다음 선분이 겹치지 않는 경우, 마지막 선분 구간으로만 판별한다. 전제상 두 선분이 서로 겹치므로 다음 선분 구간을 저장한다.
• 둘 모두에 해당하지 않는 경우 : 현재 존재하는 꽃들의 선분으로는 현재 전 구간을 커버할 수 없다. 따라서 0을 출력하고 종료한다.

 

마지막으로, 시작점이 3월 1일인지, 끝점이 11월 30일을 넘는지를 판별하면 끝.

 

풀이 코드

import sys
input = sys.stdin.readline
month_list = [31, 30, 31, 30, 31, 31, 30, 31]

def cal_days(month, days) :
  if month < 0 :
    return 0
  if month > 8 :
    return 276
  if month == 0 :
    return days
  return cal_days(month-1, days+month_list[month-1])

day_list = list() # cal_days 11.30 : 275

N = int(input())
for _ in range(N) :
  sm, sd, em, ed = map(int, input().split())
  sd = max(1, cal_days(sm-3, sd))
  ed = min(275, cal_days(em-3, ed)-1)
  if sd == 276 or ed == 0 or sd > ed :
    continue
  day_list.append((sd, ed))

day_list.sort(key = lambda x : (x[0], -x[1]))
flower_list = list()
for sd, ed in day_list :
  if not flower_list :
    flower_list.append((sd, ed))
  elif flower_list[-1][0] <= sd and ed <= flower_list[-1][1] :
    continue
  elif len(flower_list) > 1 and ( sd <= flower_list[-2][1] or flower_list[-2][1] + 1 == sd ) :
    if ed > flower_list[-1][1] :
      flower_list[-1] = (sd, ed)
  elif flower_list[-1][1] >= sd or flower_list[-1][1] + 1 == sd:
    flower_list.append((sd, ed))
  else :
    break
if not flower_list or flower_list[0][0] != 1 or flower_list[-1][1] < 275 :
  print(0)
else :
  print(len(flower_list))

풀이 완료!