백준 2457 [공주님의 정원] 파이썬

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

import sys

# 각 달의 일수를 딕셔너리로 저장합니다. (윤년은 고려하지 않습니다. 문제에서 필요 없습니다.)
days = {1: 31, 2: 28, 3: 31, 4: 30, 5: 31, 6: 30, 7: 31, 8: 31, 9: 30, 10: 31, 11: 30, 12: 31}

# 3월 1일부터 시작 가능 여부와 11월 30일까지 도달 가능 여부를 나타내는 플래그입니다.
is_end_ok = False
is_start_ok = False

# 꽃의 개수 N을 입력받습니다.
N = int(sys.stdin.readline())

flowers = [] # 꽃들의 개화 및 낙화 날짜를 저장할 리스트입니다.

# 각 꽃의 정보를 입력받고, 날짜를 1월 1일부터의 누적 일수로 변환합니다.
for _ in range(N):
    start = 0 # 꽃의 개화 누적 일수
    end = 0   # 꽃의 낙화 누적 일수
    start_m, start_d, end_m, end_d = map(int, sys.stdin.readline().split())

    # 개화 날짜를 누적 일수로 계산합니다.
    for i in range(1, start_m): # 1월부터 시작 월의 전 달까지의 일수를 더합니다.
        start += days[i]
    start += start_d # 시작 월의 일수를 더합니다.

    # 낙화 날짜를 누적 일수로 계산합니다.
    for i in range(1, end_m): # 1월부터 종료 월의 전 달까지의 일수를 더합니다.
        end += days[i]
    end += end_d # 종료 월의 일수를 더합니다.
    
    # 계산된 누적 일수를 flowers 리스트에 추가합니다.
    flowers.append([start, end])

# 꽃들을 개화 시작일(오름차순)을 기준으로 정렬하고, 시작일이 같으면 낙화일(오름차순)을 기준으로 정렬합니다.
flowers = sorted(flowers, key=lambda x: [x[0], x[1]])

i = 0 # flowers 리스트를 탐색하는 인덱스
curr_e = 0 # 현재까지 꽃들이 커버하는 마지막 날짜 (최초 3월 1일 커버를 위함)

# 3월 1일 (누적 일수 60)을 커버하는 초기 꽃들을 찾습니다.
# flowers 리스트를 순회하며 3월 1일 이전에 피는 꽃들 중 가장 늦게 지는 꽃을 찾습니다.
while flowers and i < N and flowers[i][0] <= 60:
    # 만약 현재 꽃이 3월 1일 (누적 일수 60) 이후에 진다면, 시작 조건 만족 가능성이 있습니다.
    if flowers[i][1] >= 60:
        is_start_ok = True # 시작 조건 만족 플래그를 True로 설정합니다.
        curr_e = max(curr_e, flowers[i][1]) # 3월 1일을 커버하는 꽃들 중 가장 늦게 지는 날짜를 갱신합니다.
    i += 1 # 다음 꽃으로 이동합니다.

ans = 1 # 선택된 꽃의 개수 (초기에 하나의 꽃이 선택될 경우를 가정)

# 만약 현재 커버하는 날짜가 11월 30일 (누적 일수 334)보다 크다면, 이미 종료 조건 만족입니다.
if curr_e > 334:
    is_end_ok = True

# 시작 조건과 종료 조건 모두 만족 여부를 확인합니다.
is_avail = is_start_ok and is_end_ok
len_f = len(flowers) # flowers 리스트의 길이를 미리 저장합니다.

# 만약 flowers 리스트가 비어있지 않고, 아직 시작/종료 조건이 모두 만족되지 않았다면 탐색을 계속합니다.
if flowers and not is_avail:
    # 11월 30일(334)을 넘을 때까지 꽃을 선택하는 그리디 탐색을 시작합니다.
    while i < len_f:

        s, e = flowers[i] # 현재 꽃의 시작일과 종료일입니다.

        # 만약 현재 꽃의 시작일이 현재 커버하는 날짜(curr_e)보다 크다면,
        # 즉, 중간에 꽃이 없는 기간이 생긴다면 더 이상 연결할 수 없으므로 종료합니다.
        if not s <= curr_e:
            is_end_ok = False # 종료 조건 만족 불가로 설정합니다.
            break

        j = 1 # 현재 인덱스(i)부터 탐색할 꽃의 개수를 세는 변수입니다.
        # 현재 커버하는 날짜(curr_e) 내에 시작하는 모든 꽃들을 검토하여
        # 그 중 가장 늦게 지는 꽃의 낙화일을 찾습니다.
        while i + j < len_f and flowers[i + j][0] <= (curr_e):
            e = max(e, flowers[i + j][1]) # 현재까지 찾은 꽃들 중 가장 늦게 지는 날짜를 갱신합니다.
            j += 1 # 다음 꽃으로 이동합니다.

        # 현재 커버하는 마지막 날짜를 가장 늦게 지는 꽃의 낙화일로 갱신합니다.
        curr_e = e
        # 꽃을 하나 선택했으므로 선택된 꽃의 개수를 증가시킵니다.
        ans += 1
        # 다음 탐색을 위해 인덱스를 업데이트합니다. (j는 현재 시점에서 건너뛴 꽃의 개수)
        i += j

        # 만약 현재 커버하는 날짜가 11월 30일 (334)을 넘었다면, 종료 조건 만족입니다.
        if curr_e > 334:
            is_end_ok = True
            break # 루프를 종료합니다.

# 최종적으로 시작 조건과 종료 조건 모두 만족하는지 확인합니다.
is_avail = is_start_ok and is_end_ok

# 결과 출력
if is_avail:
    print(ans) # 만족하면 최소 꽃의 개수를 출력합니다.
else:
    print(0) # 만족하지 못하면 0을 출력합니다.

그리디 하게 가장 먼저 꽃이 피는순서대로 정렬 후, 해당 꽃이 지기전에 피는 꽃들중 가장 늦게 지는 꽃을 다음에 피울 꽃으로 정한다.

이어지지 않으면 Fail 처리, 3월1일부터 11월 30일까지 꽃이 이어진다면 Success 처리 해주면 된다.

 

 

n = int(input())
f = [list(map(int, input().split())) for _ in range(n)]
f.sort()

i = 0
result = 0
latest_end = (3, 1) # 3월 1일부터 체킹

while i < n:
    sm, sd, em, ed = f[i]
    if (sm, sd) <= latest_end < (em, ed):
        max_end = (em, ed) # 현재 심을 수 있는 꽃들 중 가장 마지막에 지는 꽃 찾기 시작
        while i < n-1: 
            nsm, nsd, nem, ned = f[i+1]
            if latest_end < (nsm, nsd): # 현재 심을 수 있는 꽃이 i번째까지라면 종료
                break
            if max_end < (nem, ned):
                max_end = (nem, ned)
            i += 1
            
        # 찾은 꽃 심기
        result += 1
        latest_end = max_end
        
        # 11월 30일까지 모두 심었다면 종료
        if (11, 30) < latest_end:
            print(result)
            exit(0)
    i += 1

print(0)

https://velog.io/@minjungh63/Python-%EB%B0%B1%EC%A4%80-2457%EB%B2%88-%EA%B3%B5%EC%A3%BC%EB%8B%98%EC%9D%98-%EC%A0%95%EC%9B%90

[Python] 백준 2457번: 공주님의 정원

깔끔하게 해결하신 분의 풀이가 있어 첨부한다.