[Python] 2457 공주님의 정원

1. 문제 📚

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

2457번: 공주님의 정원

2. 입출력 예 📋

3. 알고리즘 ✅

이 문제는 조건이 2가지이다

처음엔 날짜계산을 일일히 하는 바람에 분기문이 헷갈려서 이틀이나잡고있었다; 

구글링을 통해 힌트를 얻고 다시 내 로직으로 풀어봤당

 

조건1) 3/1 ~ 11/30 까지 매일 한가지 꽃 

날짜는 월 * 100을 해주어 비교가 쉽도록 바꿔주었다

 

또한,

3/1 일 이전에 심을 수있는 꽃은 301 으로 통일해주고,

12/1일 이후에 심을 수 있는 꽃은 1201로 통일해주어서

 

조건1에 맞지않는 것은 한번에 쳐 낼 수 있도록 로직을 구현했다 ! 

 

조건2) 가능한 적게 -> 가능한 날짜가 길도록 꽃을 심어주면 됨 -> 그리디

301에서 가능한 날짜가 가장 긴 꽃을 찾아 start해주었다. 

 

정리하자면

1. 입력 받을 때, 3/1일 이전에 심은 꽃은 모두 301로 변경, 12/1일 이후는 1201으로 포맷

2. 꽃이 필 시기를 기준으로 정렬

3. 처음 시작을 가장 오래 지지 않는 꽃으로 선택하여 now_end로 초기화한다

4. for문을 돌아가면서 현재 심은 꽃보다 가장 오래 지지않는 꽃을 찾아

temp_start, temp_end를 찾는다.

5. now_start 와 temp_start 다르다면 새로운 꽃을 심을 수 있는 것이므로 plant +1을 해준다

6. 처음 시작이 301이고 마지막으로 끝난 숫자가 1201이면 plant 갯수를 출력

아니라면 조건을 충족하지 않는 것이므로 0을 출력해준다.

4. 소스코드 💻

import sys

input = sys.stdin.readline

N = int(input())

cal = []
for _ in range(N):
    start_month, start_day, end_month, end_day = map(int, input().strip().split())
    cal.append([start_month * 100 + start_day, end_month * 100 + end_day])

cal.sort(key=lambda x: x[0])

# 1. 3/1일 이전은 301로 변경 12/1일 이후는 1201로 변경
cal_format = []
for i in range(N):
    table = []
    if cal[i][0] <= 301:
        table.append(301)
    else:
        table.append(cal[i][0])

    if cal[i][1] >= 1201:
        table.append(1201)
    else:
        table.append(cal[i][1])
    cal_format.append(table)

now_start = cal_format[0][0]
now_end = cal_format[0][1]
start_index = 0

plant = 1

# 2. 처음 시작을 가장 오래 지지 않는 꽃으로 선택하여 now_end로 초기화한다
for i in range(1, N):
    if cal_format[i][0] != 301:
        break

    if now_start == 301:
        now_end = max(now_end, cal_format[i][1])
        start_index = i

temp_start = now_start
temp_end = now_end

count = 0

# 4.  현재 심은 꽃보다 가장 오래 지지않는 꽃을 찾아 temp_start, temp_end를 찾는다
while True:
    if start_index >= N - 1:
        break

    for i in range(start_index + 1, N):
        # 조건1) 하루라도 공백기가 생기면 안되니, 현재 심을 꽃이 now_end 보다 작아야함 
        # ex) 현재 심을 꽃 502 <= 503 now_end
        # 조건2) 더 오래 심을 수 있어야지 최소의 꽃을 심을 수 있음
        # 조건3, 4) 기존에 있던 temp 보다 더 많이 갈 수 있는 곳이 최선임
        if cal_format[i][0] <= now_end \
                and cal_format[i][0] >= temp_start\
                and cal_format[i][1] >= temp_end:
            temp_start = cal_format[i][0]
            temp_end = cal_format[i][1]
            start_index = i

    if now_start != temp_start and now_end != temp_end:
        # 최종적으로 심음
        plant += 1
        now_start = temp_start
        now_end = temp_end
    else:
        start_index += 1

    # 더 볼 필요없음
    if now_end == 1201:
        break

if cal_format[0][0] == 301 and now_end == 1201:
    print(plant)
else:
    print(0)

 

 

내가 삽질하면서 도움이 됐던 반례이다 〰️〰️

11
2 28 8 16
6 18 7 9
9 5 10 25
4 22 8 25
5 22 6 13
8 18 9 16
4 29 10 4
8 23 11 25
6 26 12 1
3 3 10 19
8 3 10 11

ans: 2

끝!