[백준 2457번] 공주님의 정원(python)

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

2457번: 공주님의 정원

비슷한 문제로 강의실이 있었습니다.

2022.07.13 - [알고리즘 공부] - [백준 11000번] 강의실 배정(파이썬)

[백준 11000번] 강의실 배정(파이썬)

강의실과 다른 점은

끝 지점이 끝난 이후부터 받는 게 아니라

'끝 지점이 끝나기 전부터도 받을 수 있다'라는 점.

이게 뭔소리인지 보면

 

강의실

1-3

4-6

2-7

 

-->1-3을 받으면

강의실이 1-3까지 사용중이므로

2-7은 받지 못하고 4-6을 받아야한다.

 

공주의 정원

1-3

4-6

2-7

 

-->1-3을 받는다쳐도

2-7를 받을 수 있다.

어찌되었든 꽃이 하나 이상 필 수 있고

1-3 2-7 이렇게 받을 때

꽃이 가능한 오래 필 수 있다.

 

이걸 어떻게 구현할지 난감한 부분이었습니다.

이 부분은 백준 질문하기 게시판을 참고했습니다.

 

저는 now라는, 현재의 시작점을 나타내는 변수를 지정했습니다.

꽃을 탐색하면서

꽃의 시작점이 now이하이면서

꽃의 끝점이 now보다 크면 

임시 리스트에 끝점을 저장합니다.

만약에 리스트가 하나라도 있을 경우,

now를 리스트의 최댓값으로 갱신합니다.

이런 식으로 쭉 나아가면

끝점을 최대한으로 두면서

필요한 꽃만 찾을 수 있습니다.

 

#백준 2457번 공주님의 정원

t_one=[1,3,5,7,8,10,12]
t_zero=[4,6,9,11]


def cal(m,n):
    answer=0

    while m>0:
        m-=1
        if m in t_one:
            answer+=31
        elif m in t_zero:
            answer+=30
        elif m==2:
            answer+=28

    return answer+n


N=int(input())
flower=[]
for i in range(N):
    s1,s2,f1,f2=map(int,input().split())
    flower.append([cal(s1,s2),cal(f1,f2)])

flower.sort(key=lambda flower:flower[0])
s=cal(3,1)
f=cal(11,30)


now=s
answer=0


start_index=0
temp=[]

while True:

    for i in range(start_index,N):
        if flower[i][0]<=now and flower[i][1]>now:
            temp.append(flower[i][1])
            start_index=i+1
    if temp:
        now=max(temp)
        answer+=1
        temp=[]
    else:
        break
    if now>f:
        break
if now>f:
    print(answer)
else:
    print(0)

이 문제는 부등호로 헤매기 쉬운 문제입니다.

질문글들을 참고하면

부등호 때문에 헤맸다는 말들이 많습니다.

출력을 판단할 때,

now>f(11월 30일)이렇게 되는 이유는

'11월 30일까지' 꽃이 피워있어야 하기 때문입니다.

문제를 잘 읽어보면

'끝지점부터 꽃이 진다'라는 걸 알 수 있습니다.

그래서 저같은 경우에는

f초과라고 지정을 했습니다.

 

그리디 알고리즘에 대한

다양한 접근을 공부할 수 있는 문제였습니다.