[22991] 수요응답형 버스 (박제용)

화려한 그의 이퀄라이저

사실 그리디 전략자체는 쉽게 떠올릴 수 있는데 구현 한번 꼬이면 디버그가 어려웠던 문제.

 

 

22991번: 수요응답형 버스

배차 요청이 N개, 버스 배차가 M개가 주어진다. (1 <= N, M <= 200,000)

여기서 배차 요청을 최대한 버스와 1:1로 매칭시켜줘야 한다.

탑승인원이 버스 정원보다 적거나 같아야하고

버스의 도착시간이 최대 대기 가능 시간보다 작거나 같아야하는데 사실 정렬한번 하고 투포인터로 긁어나가면 빠르게 풀 수 있는 문제였다.

 

우선 실수한거 하나, 투포인터 구현을 제대로 안했다. 종종 생각없이 투포인터를 중첩for문으로 구현하곤 했는데 여기서 실수를 범해서 O(NM)의 TLE코드를 만들어 버렸다. (정답은 O(N+M)으로 간단하게 풀린다)

 

그리고 그룹에 너무 연연했다.

풀이는 한 버스에 대하여 받아들일 수 있는 요청을 시간 또는 정원 순으로 나열해서 받을 수 있을 때 까지 받은후에,

정원이 넘치면 다음 버스에 대하여 이 과정을 반복하는 것이다.

그런데 곰곰히 생각해보면 정원이 넘친경우 다음 버스는 이전 버스보다 정원이 크므로 이전 버스에서 받은 요청을 그대로 넘겨받을 수 있었다.

 

그러면 multiset배열이 아니라 그냥 multiset 변수 하나두고 재활용하면 됬었을텐데 삽질을 거하게 한 것 같다.

 

그런 의미에서 앞으로 greedy와 two-pointer를 연습해야겠다.

 

https://github.com/Hesh0629/solved_boj_problems_in_army/blob/7126b5cb412589f9a4bf027420c50d190f87a8d6/boj/22991.cpp