백준 2118 두 개의 탑 Kotlin (투 포인터 + 이분 탐색)

문제 출처 : https://www.acmicpc.net/problem/2118

2118번: 두 개의 탑

문제

1번부터 N번까지의 지점이 있다. 각각의 지점들은 차례로, 그리고 원형으로 연결되어 있다. 이 지점들 중 두 곳에 두 개의 탑을 세우려고 하는데, 두 탑의 거리가 최대가 되도록 만들려고 한다.

지점들이 원형으로 연결되어 있기 때문에, 두 지점 사이에는 시계방향과 반시계방향의 두 경로가 존재한다. 두 지점 사이의 거리를 잴 때에는, 이러한 값들 중에서 더 작은 값을 거리로 한다.

연결되어 있는 두 지점 사이의 거리가 주어졌을 때, 두 탑의 거리의 최댓값을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 지점의 개수 N(2 ≤ N ≤ 50,000)이 주어진다. 다음 N개의 줄에는 차례로 두 지점 사이의 거리가 양의 정수로 주어진다. 전체 거리의 총 합은 1,000,000,000을 넘지 않는다.

출력

첫째 줄에 답을 출력한다.

알고리즘 분류

• 누적 합
• 두 포인터

풀이

누적 합 + 투 포인터 + 이분 탐색 문제이다.

우선 문제를 파악하자.

원형으로 연결되어 있는 지역들에서, 두 개의 지역을 골라 탑을 세운다.

이때 두 개의 탑은, 원형으로 연결되어있기 때문에 시계 방향, 반시계 방향 두 가지 경로가 가능하다.

두 가지 경로가 가능하다는 것은 두 개의 거리값이 있다는 것을 의미하고, 두 거리 값 중에 더 짧은 거리를 사용해야 한다고 한다.

정리하면,

1. 두 개의 탑을 고른다.

2. 두 탑의 거리의 두 거리(시계 방향, 반시계 방향) 중 짧은 거리를 선택한다.

3. 이렇게 고른 두 탑의 짧은 거리가 가장 큰 거리인 두 개의 탑을 찾는다.

 

짧은 거리중 가장 큰 값이라고 생각하면 헷갈리니까,

두 탑의 거리가 최대가 되는 어떠한 a,b라는 두 탑을 찾는데,

짧은 거리란 그냥 a,b 사이의 거리를 정하는 조건이라고만 생각하자.

 

우선 시계, 반시계 거리의 성질을 보면,

시계 방향으로 점점 더 멀리 있는 탑을 선택한다면 시계 방향 거리는 늘어나고, 반시계 방향 거리는 줄어든다.

여기까진 쉽게 알 수 있을 것이다.

근데 이걸 어떻게 활용하냐가 문제다.

 

 

첫 번째 탑으로 임의의 지역 C를 선택했다고 하자.

이제 두 번째 탑을 골라야 한다. 시계방향으로 가까운 거리부터 선택해 보자.

두 탑의 거리(두 방향 중 짧은 거리)를 X라 하고, X를 빨간색으로 처리한다.

C-D : 시계 = 3, 반시계 = 12

C-E : 시계 = 7, 반시계 = 8

C-A : 시계 = 12, 반시계 = 3

C-B : 시계 = 13, 반시계 = 2

그래프는 그리고 값을 모두 정리해서 보는 게 직빵이다.

위에 빨간 숫자들을 보자.

X가 점점 커지다가, 시계 방향 거리가 반시계 방향 거리보다 커지는 순간부터 X는 점점 작아진다.

우리는 큰 X값을 찾아야 하기 때문에 X가 점점 작아진다면 더 이상 검사할 필요가 없는 것이다.

 

여기까지 했을 때, 투 포인터의 개념으로 C를 선택하고 나머지 지점 하나를 선택하는 것으로 두 탑을 고를 수 있고,

누적 합의 개념으로 두 탑의 거리를 구할 수 있다.

(C,E를 선택했다고 하면 시계 방향 = preSum[E]-preSum[B], 반시계 방향 = preSum[E] - (preSum[E]-preSum[B]))  

하지만 아직 첫 번째 탑을 고르는 경우의 수 5만, 그리고 나머지 탑을 고르는 경우의 수 5만 이하(시계 방향 거리가 반시계 방향 거리보다 커지는 순간까지)이므로, 문제에서 원하는 답은 찾을 수 있지만 1초 내에 답을 구할 순 없다.

여기서 이분 탐색의 개념이 들어간다.

첫 번째 탑을 5만 개 고르고, 나머지 탑을 고르는 것을 이분 탐색으로 고를 수 있다.

 

첫 번째 탑으로 A를 골랐다고 하면, 두 번째 탑의 범위는 B~E이다.

start = B

end = E

mid = (B+E)/2

알파벳으로 했지만 실제로는 인덱스를 활용한다.

mid는 두 번째 탑이다.

mid라는 두 번째 탑을 골랐을 때 시계, 반시계 거리를 구하고 만약 시계 거리가 반시계보다 더 작다면 mid를 늘리고, 시계 거리가 반시계보다 더 크다면 mid를 줄인다.

 

이렇게 첫 번째 탑 고르기 5만 * 두 번째 탑 고르기 log5만으로

총 O(5만log5만)의 시간 복잡도로 통과할 수 있다.

 

좋은 문제 리스트에 추가~

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()
lateinit var preSum: IntArray
fun main() = with(System.out.bufferedWriter()) {
    //input
    val n = getInt()
    preSum = IntArray(n+1)
    for(i in 1 .. n){
        preSum[i] = preSum[i-1] + getInt()
    }
    //solve
    var answer = 0
    for(i in 1 .. n){
        var s = i
        var e = n
        while(s<=e){
            val mid = (s+e)/2
            //i부터 mid까지 정방향, 역방향 중에 작은 값 사용
            val originDis = preSum[mid] - preSum[i-1]
            val reverseDis = preSum[n] - originDis
            val minDis = originDis.coerceAtMost(reverseDis)
            answer = answer.coerceAtLeast(minDis)
            if(originDis < reverseDis){
                s= mid+1
            }
            else{
                e = mid-1
            }
        }
    }
    //output
    write("$answer")
    close()
}