[Python] 백준 #2457 공주님의 정원(탐욕 알고리즘)

#2457 문제는 탐욕 알고리즘을 이용해서 풀 수 있습니다.  탐욕 알고리즘은 정렬을 하고, 조건에 맞는 경우에는 우선 선택 과정을 하게 됩니다.

 

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

2457번: 공주님의 정원

문제는 공주님의 정원에 늘 꽃이 한종류 이상 피어있게 하면서, 최소의 꽃을 정원에 두는 것입니다.  최소의 꽃의 개수를 구하는 것이 목표입니다.

 

princess garden

 

이 문제를 풀기 위해서는 (꽃 피는 날짜, 꽃이 지는 날짜) 쌍을 적절하게 유지해야 합니다.

일단 "꽃 피는 날짜"를 기준으로 해서 정렬을 합니다.

 

 

현재 하얀색 선은 이미 완료가 된 꽃입니다.

빨간색 선은 카운트가 된 꽃입니다.  그러면 마지막 완료지점에서부터 빨간색 꽃의 지는 시점까지를 (start, end)라고 설정합니다.

이 때, A 꽃이 들어올 때에는 시작 지점이 start보다 작고, end 지점만 빨간색 꽃의 지는 시점보다 크므로, 카운트를 증가하지 않고 end 값만 바꿉니다.  하얀색 꽃 다음에 빨간색 꽃이었지만, A 파란꽃이 대신하게 되는 것입니다.  이렇게 되면 빨간색 꽃이 필요없게 되는 것입니다.  카운트는 바뀌지 않습니다.  하지만 B의 파란색 꽃이 들어오면, B의 파란색 꽃은 하얀색 다음에 꽃이 없는 공백이 생기기 때문에 반드시 카운트가 증가해야 합니다.  B의 파란색 꽃은 이전 꽃이 지는 지점부터 B 파란색꽃이 지는 지점까지가 새로운 (start, end)가 됩니다.

 

이번에는 파이썬을 이용해 만들어보았습니다.  조금 잘못 짠 부분도 있긴 한데, 여하튼 통과는 되었습니다.  11월 30일 이후에 꽃이 두가지 종류가 피는 경우가 있다면 통과가 되지 않았을겁니다.

 

예를 들어서 다음과 같은 경우에는 정답은 1이지만, 제 프로그램 답은 2가 나옵니다.

3
1 1 12 1
11 10 12 14
12 10 12 30

 

제가 작성한 소스입니다.

"""
//    baekjoon #2457
//    Author: by Aubrey Choi
//    Date: 2023-03-30
"""
n = int(input())
arr = [tuple(map(int, input().split())) for i in range(n) ]
arr.sort()

cnt = 0
start, end = (3, 1), (3, 1)
for v in arr:
    if v[:2] > start:
        if end == start: break
        cnt += 1
        start = end
        if v[:2] > start: break
    if v[2:] > end: end = v[2:]
if end < (11, 31): cnt = 0
elif start < (11, 31): cnt += 1

print(cnt)