티스토리 뷰

공부

KOI 2014 - 버스

구사과 2014. 10. 15. 12:02

http://www.jungol.co.kr/prog/Hanal/hanalView.php?qs_code=2796
에서 채점할 수 있다. (File IO를 사용하니 입출력에 유의하라)


3달 전 본선에서 풀려 했을 때는 m^2를 짜고 최적화를 하면 될 줄 알았는데

전혀... 그런 풀이가 아니었다 ㅋㅋㅋ

나온 다음에, 정렬 하는거 까지는 눈치챘지만 그 이후 아이디어는 잘못 생각했었음..


얼마 전에 다시 생각해봤는데 풀이는 간단하다.

먼저 버스의 시작점 순으로 소트한 다음에, 시작점이 전 원소보다 큰데 끝 점이 전 원소보다 작은 경우는 존재하지 않는다는 것을 알면 된다.

결과적으로 실제 버스의 집합은 시작점과 끝 점 모두가 증가하는 형태일 것이다.

그렇기때문에 시작점 순으로 버스를 쭉 넣은 다음에... 만약에 현재 버스 집합의 최종 끝점이 자신보다 작으면 이번 버스는 누군가에 속하는 거고, 버스 집합에 넣지 않으면 된다.

(아, 그리고 시작점이 같은 쿼리에 대해서는 어떻게 정렬해야 할까?)


원 처리 역시 간단하게 가능하다.

뒷점 > 앞점으로 가는 버스에 경우 뒷점 -> 앞점 + N 으로 가는 버스라고 생각하면 된다.

그러면 위 상황과 똑같이 처리가능하다.

하지만, 이 경우 앞에 있는 버스의 일부는 뒤에 추가된 버스에 의해서 사라질 것이다.

즉, 뒤에 추가된 버스 중 끝점이 가장 큰 놈 보다, 앞에 있는 버스들의 끝점이 작다면, 이들은 버스 집합에 들어가지 않는다.


이를 알면 간단히 구현할 수 있다.

다만 정답을 번호 순대로 출력하기 위해서는 다시 번호 순으로 정렬해서 출력해야 할 것이다.

본인은 deque를 써서 구현했는데, 입맛대로 하면 된다.


예제 소스 : http://pastebin.com/CkVLG5u3

'공부' 카테고리의 다른 글

Maximum subarray algorithm (Kadane's algorithm) 유도하기  (5) 2014.11.08
트리의 지름 (Diameter of tree)  (2) 2014.11.01
KOI 2014 - 버스  (3) 2014.10.15
STL priority queue 활용법  (17) 2014.09.13
비트필드와 완전 탐색 최적화 (Bit DP)  (0) 2014.09.07
KOI 2013 - 전봇대  (1) 2014.08.30
댓글
  • 프로필사진 실제 버스의 집합은 시작점과 끝 점 모두가 증가하는 형태라는게 무슨 뜻인지 좀 더 자세히 알 수 있을까요??
    좀 이해가 안되서...
    2017.07.07 13:59
  • 프로필사진 구사과 두 버스 노선을 비교했을 때, 시작 점이 큰 쪽이 끝 점도 크고, 시작 점이 작은 쪽이 끝 점도 작다는 뜻입니다. 2017.07.09 02:07 신고
  • 프로필사진 ㄴㅇㄱ 왠지 입력값 범위 보고 파라메트릭 서치 같았는데 아니었네요 ㅋㅋㅋ 2019.07.18 17:33
댓글쓰기 폼
공지사항
Total
454,711
Today
0
Yesterday
408