[코테] 백준 그리디 2457번 문제

2457번 : 공주님의 정원

문제 링크

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

문제 설명

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

총 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일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오.

입력

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

출력

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

문제 풀이

아래 코드를 제출할 때는 pypy3로 제출해야 통과한다. python3로 제출하면 시간초과 발생.. 아직 공부해야할 길이 멀다.

from heapq import heappush, heappop

arr = []
candidate = []
count = 0
bloom = [0] * 275

# 월일을 숫자로 변환하는 함수
def CalDays (month, day) :
    days = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    
    # 현재월일에 3월1일까지 값을 빼기
    value = sum(days[:month-1]) + day - sum(days[:2]) - 1 
    
    if value < 0 :
        value = -1 
    
    # 275 (12월 1일) 까지만 표현
    elif value > sum(days[:11]) - sum(days[:2]) : 
        value = sum(days[:11]) - sum(days[:2]) 
        
    return value

# 꽃 개수 입력
N = int(input())

# 꽃들의 정보 입력하고 heap 자료구조를 사용하여 배열에 저장
for i in range(N) : 
    st_mon, st_day, en_mon, en_day = map(int, input().split())
    
    # 지는 날이 3월 1일보다 큰 꽃들만 저장
    if CalDays(en_mon, en_day) > 0 : 
        heappush(arr, (CalDays(st_mon, st_day), -CalDays(en_mon, en_day)))

# 맨처음 배열 항목의 피는 날짜가 0보다 크면 count 0으로 저장
if arr[0][0] > 0 :
    count = 0

else : 
    
    # 피는 날이 3월 1일 이전인 꽃들을 후보 배열에 저장
    while arr and arr[0][0] <= 0 : 
        start, end = heappop(arr)
        heappush(candidate, (end, start))
    
    # 3월 1일 이전에 피는 꽃들 중 가장 오래 피는 꽃을 last_flower에 저장하고 count 1 올리기
    end, start = heappop(candidate)
    candidate = []    
    last_flower = (start, -end)
    bloom[:-end] = [1] * -end 
    count += 1
    
    # 배열 항목이 남아있고, 현재 추가한 꽃들이 11월 30일까지 피기 전까지 
    while arr and sum(bloom) < 275 :
        start, end = heappop(arr)
        
        # 후보 넣는 기준 start가 last_flower end값보다 작거나 같고 end가 last_flower의 end보다 크면
        if start <= last_flower[1] and -end > last_flower[1] :
            heappush(candidate, (end, start))
            
        # 남은 arr 항목이 없다면 지금까지 후보중 가장 end값이 큰 애를 lasf_flower로 저장하고 bloom 배열에 값을 넣음
        if candidate and len(arr) == 0 :
            end, start = heappop(candidate)
            bloom[start:-end] = [1] * (-end - start)
            count += 1
            
        # 남은 arr start 값이 last_flower end값보다 크먄 현재 후보중 가장 end 값이 큰 애를 last_flower로 저장하고 bloom 배열에 값을 넣음
        elif arr and candidate and arr[0][0] > last_flower[1] : 
            end, start = heappop(candidate)
            candidate = []
            
            bloom[start:-end] = [1] * (-end - start)
            last_flower = (start, -end)
            count += 1
        
if sum(bloom) == 275 : 
    print(count)

else : 
    print(0)