[Algorithm] 2457. 공주님의 정원

2457 : 공주님의 정원(그리디)

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

• 문제 티어 : G3
• 풀이 여부 : Failed
• 소요 시간 : 26:51

정답 코드

import sys
input = sys.stdin.readline

N = int(input())
arr = []
for _ in range(N):
  start_m, start_d, end_m, end_d = map(int, input().rstrip().split())
  arr.append([start_m, start_d, end_m, end_d]) 

arr.sort(key= lambda x: (x[0], x[1], -x[2], -x[3])) # 시작일자와 종료일자를 기준으로(시작달 : 빠른 순, 종료 달 : 느린 순)
start_date, end_date = (3, 1), (11, 30)
latest_date, next_start = (0, 0), (0, 0) # 종료 날짜, 다음 꽃을 심을 날짜

cnt, i = 0, 0

while start_date <= end_date and i < N:
  valid = False
  # 3/1일부터 꽃을 피울 수 있는 조건 찾기
  while i < N and (arr[i][0], arr[i][1]) <= start_date:
    if (arr[i][2], arr[i][3]) > latest_date: # 종료날짜가 가장 늦은 것 찾아서 갱신
      latest_date = (arr[i][2], arr[i][3])
      next_start = (arr[i][0], arr[i][1])
      valid = True
    i += 1 # 다음 꽃 개화시기 순회
  if valid:
    start_date = latest_date # start_date를 갱신해 end_date까지 순회
    cnt += 1
  else:
    break

if start_date <= end_date:
  print(0) # 모든 기간을 커버할 수 없는 경우 : 누적해서 갱신한 시작 일자가 종료 일자보다 적음
else:
  print(cnt)

접근 방식

그리디를 사용해서 푸는 문제임은 알았지만! 구현 과정에서 삐끗해서 한참 고민했던 문제다.

문제의 두 조건을 보면,
1. 공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.
2. 정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다.
조건을 만족하는 범위 내에서 최소한의 꽃의 개수를 구해야 하므로 그리디로 접근하는 것이 맞다고 생각했다.

입력값을 받은 다음, 시작일자는 빠른 순으로, 종료일자는 느린 순으로 정렬을 해준다. → O(NlogN)
그 다음 4개의 튜플(또는 배열)형태의 변수를 만들어준다.

• 3/1 : start_date, 11/30 : end_date → 문제 조건의 3/1 시작일자와 11/30 종료일자
• 0/0 : latest_date, 0/0 : next_start → 선택한 시작일자가 종료되는 값, 다음 시작일자

문제를 풀기 위해 start_date를 갱신해가면서 end_date보다 커질 때까지 반복해줬다.
더불어 조건을 만족하는 꽃을 선택했으면, 다음 꽃을 순회하기 위해 i변수로 arr을 순회한다. (i < N)

  while i < N and (arr[i][0], arr[i][1]) <= start_date:
    if (arr[i][2], arr[i][3]) > latest_date: # 종료날짜가 가장 늦은 것 찾아서 갱신
      latest_date = (arr[i][2], arr[i][3])
      next_start = (arr[i][0], arr[i][1])
      valid = True
    i += 1 # 다음 꽃 개화시기 순회

위 코드와 같이 start_date와 latest_date, next_start를 갱신해주면서 start_date ≤ end_date 조건에 위배될 때까지 반복을 계속한다.

배운점 또는 느낀점

우와 이 문제 어려웠다… ^..^ 체크해두고 이 문제는 꼭 다시 풀어봐야겠다!