[SWEA - 9850] 의자 제공하기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXGBRbxaP7sDFAXR&categoryId=AXGBRbxaP7sDFAXR&categoryType=CODE

SW Expert Academy

진짜.. 많이 틀린 문제인데..

일단 아이디어부터 얘기해보도록 하자..

1. 일단 데이터의 수가 많은 점을 착안하자

2. 의자는 어찌되었든 주어진 숫자에 따라 앉는것이 룰이다.

3. 그렇다면, 제일 좁은 구역에 앉을 놈들을 먼저 앉히는게 좋지않을까?  

이제 착안할 점은 앉히는 기준을 생각해내는 것이다.

 

1~ a, b ~ M의 범위에 앉힐수 있다면

먼저 1~a 의 범위가 좁은 것부터 앉히고, b~M의 것들은, 이전에 처리하지 못한것들을 앉히는것에 착안했다.

이러한 범위를 찾아내는것은, 선형탐색도 있지만, 나는 이진탐색 툴인 Lower_bound, Upper_bound를 써서 문제를 해결했다.

문제 풀이는 다음과 같다.