BOJ 2887 행성 터널
www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제를 요약하자면 MST의 Cost를 구하는 문제이다. 단, 이 문제의 값 크기는 1 ≤ N ≤ 100,000 로 Naive하게 모든 행성들의 간선 거리를 구하려고 한다면 10^15가 되어 시간내에 풀지 못할 것이다. 이 문제에서 잘 봐야할 것은 터널을 연결할 때 드는 비용이다. "두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min..
BOJ 13334 철로
www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 이 문제를 단순화 시킨다면 다음과 같이 정의할 수 있다. "시작점으로부터 거리 d (d > 0) 보다 가까이 있는 도착점의 개수 중 최대 값" 그래서 시작점, 도착점을 각각 벡터에 저장하여 정렬한 뒤, 2-pointer를 사용하여 문제를 해결하였다. 시작점으로부터 거리가 d 초과인 도착점이 나올 때 까지 도착점의 index를 하나씩 늘렸고, 그에 따라 loca..