[그리디 알고리즘] 백준 2457번. 공주님의 정원 (파이썬)

백준 2457번 🔗https://www.acmicpc.net/problem/2457

2457번: 공주님의 정원

꽃들의 개화시간이 주어지고 정원에 꽃이 계속 피어있도록 꽃을 선택할 때 꽃의 최소 개수를 구하는 문제이다. 

 

백준 1514번 회의실 배정 문제와 유사하지만, 정원에 꽃이 3/1~11/30에 계속 피어있어야 한다는 조건 때문에 더 복잡했던 문제이다. 

 

🌱 코드 

import sys
input = sys.stdin.readline

N = int(input())

# 입력 및 정렬
arr = []
for i in range(N):
    a, b, c, d = input().split()
    start = a.zfill(2) + b.zfill(2)
    end = c.zfill(2) + d.zfill(2)
    arr.append([start, end]) # 3 2 -> 0302로 저장
arr.sort() # 개화시간이 빠른 순으로 정렬


sum = 0 # 선택한 꽃 개수
end = '0301'

start_idx = 0 # 남은 꽃들 중 첫 인덱스
while 1:
    if end > '1130': # 꽃들을 문제없이 다 선택한 경우
        break
    elif start_idx == N-1 and arr[N-1][1] <= '1130': # 모든 꽃이 12/01 전에 지는 경우
        sum = 0 
        break
    else:
        newend = []
        # 심을 수 있는 꽃들 중 제일 늦게 지는 꽃을 선택한다. 
        for i in range(start_idx, N):
            if arr[i][0] <= end:
                newend.append(arr[i][1]) 
            else:
                start_idx = i 
                break
        if len(newend) == 0: # 심을 수 있는 꽃이 없는 경우
            sum = 0 
            break
        else:
            end = max(newend)
            sum += 1

print(sum)

 

🌼 문제 풀이

꽃이 최소 개수가 되기 위해서는 가장 오래 펴있는 꽃들을 선택해야 한다. 

심을 수 있는 꽃들 중 제일 늦게 지는 꽃을 선택하는 방법으로 문제를 해결한다. (그리디 알고리즘)

- 피는 시간 순으로 꽃들을 정렬하여 배열을 순회한다.

- 심을 수 있는 꽃이란? 이전에 선택한 꽃의 지는 날짜보다 일찍 펴야 한다. 

- 가장 늦게 지는 꽃 선택하는 방법? 가능한 꽃들의 지는 시간을 배열에 모두 추가한 후, 최댓값을 뽑는다.

 

조건을 만족하는 꽃들을 선택할 수 없는 경우: 

1. 앞이 빈다. (3/1 이전에 피어 있는 꽃이 없다)

    → if len(newend) == 0 에서 걸러짐

2. 중간이 빈다.

    → if len(newend) == 0 에서 걸러짐

3. 끝이 빈다. (12/01 이전에 모든 꽃이 진다)

    → elif start_idx == N-1 and arr[N-1][1] <= '1130' 에서 걸러짐

 

🥀 반례 모음

https://www.acmicpc.net/board/view/86573

글 읽기 - 공듀님 반례 모음입니다.

 

 

 

공주님의 정원