[BOJ 2457] 공주님의 정원

문제

[BOJ 2457] 공주님의 정원

N개의 꽃들 중 두 조건을 만족하는 꽃 선택하기

1. 3월1일~11월30일 매일 꽃이 한 가지 이상 피어있도록
2. 꽃의 개수는 최대한 적게

구상

이전 꽃과 겹치는 꽃들 중 가장 늦게 지는 꽃(그리디) 고르기
선택되지 않은 꽃은 다음에도 선택되지 않음

코드

import sys
input = sys.stdin.readline

N = int(input()) #꽃개수<=100,000

# 노트1
# 예를 들어, 한 줄 입력이 1 1 5 31 로 들어오면
# flowers.append((101,531)) 로 저장
flowers = []
for _ in range(N):
    date = list(map(int,input().split()))
    st,en = date[0]*100+date[1],date[2]*100+date[3] 
    flowers.append((st,en))
flowers.sort()

end,tmp,idx,ans = 301,301,0,0
while end<=1130:
    '''
    # 핵심 알고리즘
    # 겹치는 꽃들 중 가장 늦게 지는 꽃 고르기
    # tmp가 갱신되지 못하는 꽃은 다음 번에도 볼 필요없기 때문에
    # idx += 1 해줘도 됨
    '''
    while idx<N and flowers[idx][0]<=end: # 노트2
        tmp = max(tmp,flowers[idx][1])
        idx += 1
    # 겹치는 꽃이 없으면 무조건 답 0
    if tmp==end:
        print(0)
        sys.exit(0)
    end = tmp
    ans += 1
print(ans)

노트

1. 날짜는 (월*100+일)로 저장하면 월말 구분할 필요가 없다.
2. while문을 쓰면 그리디한 조건을 깔끔하게 작성할 수 있다.