99클럽 코테 스터디 5일차 (BOJ 2457번 공주님의 정원)

오늘의 문제: BOJ 2457(공주님의 정원)

문제 설명

총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. 

이러한 N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다.

1. 공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.
2. 정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다. 

N개의 꽃들 중에서 위의 두 조건을 만족하는, 즉 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오. 

 

알고리즘

문제의 조건에서 가능한 꽃들의 수를 적게하라는 문장에서 그리디를 떠올리게 되었다. 입력으로 주어진 꽃들 중 3/1 전에 핀 꽃 중에 가장 나중에 지는 꽃을 선택하는 것이 꽃들의 수를 가능한 적게 하는 방법일 것이다. 그 다음 나중에 지는 꽃의 지는 날을 타겟으로 정한 후 꽃들 중에 타겟 날짜보다 먼저 피는 꽃을 조회 없으면 0을 출력한다. 타겟 날짜가 11/30일을 지나면 꽃의 개수를 출력한다. 순서대로 다시 정리해보자면

 

1. 꽃을 피는 날이 먼저인 순으로 정렬

2. 타켓 날짜를 3/1로 지정

3. 입력으로 주어진 꽃들중 피는 날이 3/1 이전으 꽃들 선택

4. 선택된 꽃들중에 가장 나중에지는 꽃 선택(타켓 날짜 변경)

5. 선택된 꽃 다음 꽃들 정렬하면서 꽃의 피는 날이 타겟날짜 보다 먼저일 경우 위의 반복 동일 진행, 타겟날짜 보다 이 후일 경우 0 출력

 

# 꽃의 피고 지는 날을 정렬하기 쉽게 숫자로 변경
def day_convert_num(month, day):
    day_num = 0
    month_li = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

    for i in range(month):
        day_num += month_li[i]
    
    day_num += day

    return day_num

n = int(input())

flower_li = []
for _ in range(n):
    st_m, st_d, end_m, end_d = map(int, input().split())
    start_num = day_convert_num(st_m, st_d)
    end_num = day_convert_num(end_m, end_d)
    flower_li.append((start_num, end_num))


sort_flower = sorted(flower_li, key=lambda x:(x[0], x[1]))
end_num = day_convert_num(11, 30)
target_end = day_convert_num(3, 1)
cnt = 0
max_end = 0

# 조건에 맞게 꽃을 심었을때 마지막 꽃의 지는날이 11월 30일 보다 커야함
while target_end <= end_num:
    candidate_li = []

    for flower in sort_flower:
    	# 꽃의 피는 날이 타겟 날짜 보다 전이여야 함 
        if flower[0] <= target_end:
            # 재차 반복시 전에 선택된 꽃 선택 방지
            if flower[1] <= max_end:
                continue
            candidate_li.append(flower[1])
        else:
            break
    
    if not candidate_li:
        cnt = 0
        break  # 무한 루프를 방지하기 위해 반복문 종료
    
    # 가장 멀리까지 피어 있는 꽃을 선택
    target_end = max(candidate_li)
    max_end = max(candidate_li)
    cnt += 1

print(cnt)