반응형
선분 위의 점
-
BOJ) 선분 위의 점알고리즘/백준 2020. 8. 28. 02:01
선분 위의 점 11663번: 선분 위의 점 첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 www.acmicpc.net 풀이 2달 전에 이 문제를 풀다가 계속 시간초과랑 오답이 번갈아 뜨면서 포기했던 문제였다. 오늘도 풀면서 3번이나 틀렸지만 결국 풀어냈다..!! 우선, 문제의 조건에 따라 각 점들은 int형으로 주어지고, 선분의 left, right 범위는 long 타입으로 주어진다. 그리고 완전탐색을 하게되면 가지치기를 엄청나게 잘하지 않는 이상은 시간초과가 뜬다고 생각했다. 그래서 binary search를 이용했다. 점들의 배열을 오..