[백준 02457] 공주님의 정원 [C/C++]

문제

오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다.

총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. (올해는 4, 6, 9, 11월은 30일까지 있고, 1, 3, 5, 7, 8, 10, 12월은 31일까지 있으며, 2월은 28일까지만 있다.)

이러한 N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다.

1. 공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.
2. 정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다. 

N개의 꽃들 중에서 위의 두 조건을 만족하는, 즉 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오. 

입력

첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, 3 8 7 31은 꽃이 3월 8일에 피어서 7월 31일에 진다는 것을 나타낸다. 

출력

첫째 줄에 선택한 꽃들의 최소 개수를 출력한다. 만약 두 조건을 만족하는 꽃들을 선택할 수 없다면 0을 출력한다.

---

풀이

꽃의 개화일( first )과 낙화일( second )을 고려하여, 3월 1일부터 11월 30일까지 연속으로 꽃이 개화할 수 있는지 확인하는 Greedy 문제다.

 

우선, 개화월/일, 낙하월/일을 입력받아 정렬하기 쉽도록 월에 100을 곱하고 일을 더해주자.

개화일과 낙화일을 기준으로 정렬해주자.

1월1일 ~ 2월28일 사이의 꽃은 필요가 없기 때문에 end를 301부터 시작해주자.

꽃이 연속으로 개화할 수 있는지 알아보기 위해, 개화한 꽃이 낙화하기 전, 또 다른 개화 가능한 꽃을 대상으로 낙화일( cur_end )이 가장 늦은 꽃을 찾아주는 과정을 반복하면 된다.

 

우선, 최종 개화일( end )이 12월 1일 미만이고, 모든 꽃에 대해 탐색이 끝났는지( idx < N )와 다음 꽃의 개화일이 end 이전으로 연속으로 꽃을 개화할 수 있는지 확인해주자.

위에서 언급한대로 개화한 꽃이 낙화전, 또 다른 개화 가능한 꽃 중

낙화일이 가장 늦는 꽃을 찾아주자. 가장 늦은 낙화일이 아닌 경우에도 볼 필요가 없기 때문에 idx를 증가시켜주어 꽃을 제외시키자.

만약, 낙화일 이전에 개화 가능한 꽃이 없다면 탐색을 중단하자. 처음부터 선택 가능한 꽃이 없는 경우는 while의 조건식에서 이미 처리했다.

처음부터 선택 가능한 꽃이 없는 경우는 이미 while의 조건식에서 처리했기 때문에 볼 필요가 없다.

가장 늦은 개화일과 갯수를 갱신하자.

만약, 탐색과정에서 while의 조건식을 만족하지 못한다면 end가 1201 미만으로 탐색이 종료될 것이다. 이때는 정답이 없기 때문에 0을 출력하면 된다.

---

소스코드

보기

---

출처

2457번: 공주님의 정원