백준 2457. 공주님의 정원

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

2457번: 공주님의 정원

 

방법을 알면 정말 쉽지만 생각이 안나면 정말 어려운 그리디 문제.

 

주어진 꽃들을 피는 날짜 기준 오름차순 정렬한다.

우리가 필요한건 3.1 ~ 11.30 까지 하루도 빠짐없이 꽃이 피도록 하는 것이다.

 

1. 그럼 우선 먼저 해야할건 3.1 이전에 피는 꽃들을 살펴봐야 한다.

그런 꽃들 중 지는 기간이 가장 긴 꽃을 고른다.

고른 꽃의 지는 날짜를 저장한다. flowerEnd 라고 해보자.

 

2. 하루라도 꽃이 안피면 안되기 때문에 꽃들 중 flowerEnd 날 보다 피는 날이 작거나 같은 꽃들을 살펴본다.

마찬가지로 그런 꽃들 중 지는 기간이 가장 긴 꽃을 고른다.

flowerEnd를 갱신한다.

 

1~2를 반복하고 만약 마지막에 flowerEnd가 11.30 보다 작거나 같다면 3.1~11.30일 모든 날에 꽃이 피는 것이 불가능한것이다.

 

기간과 기간 사이 조건을 정말 잘 생각해봐야 하는 문제 부등호를 조심하자.