Red Salmon

출처 : https://www.acmicpc.net/problem/1931

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/1931.cpp

이 문제는 전형적인 그리드알고리즘이다. 그리고 아주 기초 그리드 알고리즘이다. 

먼저 입력을 종료값기준으로 정렬시킨다. 그리고 임시 변수에 종료값을 담아 두어, 계속 비교를 한다. 그런데 여기서 시작시간과 종료시간이 같을수도 있다고 하였으니 <= 식으로 표현해야 한다. 

그런식으로 표현을 하게 되면 종료시간이 제일 빠른 녀석을 처음에 고르게 되고, 그 종료시간으로부터 다음 시작을 하면서 종료시간이 제일 빠른녀석을 고르게 되므로 최대의 경우의수를 구할수있다.

n이 10만이기때문에 재귀로는 접근이 불가하고 이런식으로 풀어야한다.

그런데 여기서 재채점이 과거에 있었는데 나역시 정답이었다가 오답이되었다. (물론 지금은 다시 정답이다.)

요점은 이렇다.

1 1

1 2

2 2

2 3

이런식의 입력이 있을때 최대 선택이 몇개가 되야하는가다. 이건 x를 한번정렬을 해주면 된다. 그래서 있는것이 stable_sort인것이다. (참고 : http://www.cplusplus.com/reference/algorithm/stable_sort/)

x를 먼저 정렬해준수 stable_sort를 써서 y정렬을 해주면 깔끔하게 해결이 된다. 과거 stable_sort와 비슷하게 구현해봤는데 정말 귀찮았었던 기억이 있다. STL을 공부해두면 여러모로 편하다.