[BOJ-2118] 두 개의 탑(JAVA)

백준 2118 두 개의 탑

 

2118번: 두 개의 탑

 

문제 설명

 

 - 1번부터 N번까지의 지점이 있다.

 

 - 각 지점들은 차례로, 그리고 원형으로 연결되어 있다.

 

 - 이 지점들 중 두 곳에 두 개의 탑을 세우려 한다. 이때 두 탑의 거리가 최대가 되도록 만들어야 한다.

 

 - 지점들 사이는 원형으로 연결되어 있기 때문에, 두 지점 사이에는 시계방향과 반시계방향의 두 경로가 존재한다.

 

 - 두 지점 사이의 거리를 잴 때에는, 이러한 값들 중 더 작은 값을 거리로 한다.

 

 - 연결되어 있는 두 지점 사이의 거리가 주어졌을 때, 두 탑 거리의 최댓값을 계산하라.

 

---

 

입력 값

 

 - 첫째 줄에 지점의 개수 N( 2 <= N <= 50,000 )이 주어진다.

 

 - 다음 N개의 줄에는 차례로 두 지점 사이의 거리가 정수로 주어진다.

 

 - 전체 거리의 총 합은 1,000,000,000을 넘지 않는다.

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 두 지점사이에 탑을 두어, 그 사이 거리가 최대가 되는 값을 리턴하는 문제이다.

 

 - 간단하게 생각해보자면, N개의 지점 중 2가지 지점을 골라 해당 지점 사이의 거리를 구하면 된다.

 

 - 이때, N가지 지점 중 2가지 지점을 고르는 경우의 수는 NC2 = N*(N-1)/2 이다.

   즉, N은 최대가 5만이기 때문에 약 12억5천만 정도가 되기 때문에 불가능하다.

 

 - 이 문제를 다시 살펴보면, 두 탑 사이의 거리 중 시계 방향과 반시계 방향 중 작은 값이 거리가 된다는 것을 알 수 있다.

 

 - 즉, 전체 거리는 정해져 있고, 두 탑 위치에 따라 더 작은 값이 거리가 된다는 것이다.

 

 - 한 점을 고정하고, 다른 하나의 점을 하나씩 늘려가면서 모든 노드를 선택한다고 가정해보자,

   이때 거리가 늘어나지 않는다면 고정된 점에서 다른 노드를 선택해도 최대 거리는 변하지 않게 된다.

 

 

   -오른쪽 거리 >= 왼쪽 거리가 되기 때문에 1번 지점에서 시작하는 두 탑의 거리는 더 이상 측정할 필요가 없다. 

    왜냐하면, 오른쪽 거리 + 왼쪽 거리 = 전체 거리인데, 그 두 거리 중 작은 값이 선택된 거리가 되기 때문이다.

     

   - 오른쪽 거리는 계속 증가하고, 왼쪽 거리는 계속 감소한다. 즉, 감소되는 왼쪽 거리가 선택된다.

     즉, 오른쪽 거리 >= 왼쪽 거리가 된 시점부터는 작은 거리가 계속해서 감소하기 때문에 최대값을 찾는 경우에서는 볼 필요가 없다.

 

 - 그렇기 때문에, 첫 번쨰 노드를 한 칸 옮겨서 계속 탐색한다.

 

 - 이 과정을 모두 탐색하면서, 가장 큰 값을 찾으면 된다.

 

 - 이때 시간 복잡도는 첫 번째 노드 N, 두 번째 노드 N 이기 때문에  O(2N) = O(N) 이 된다.

 

 

 

---

 

 

소스 코드

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(bf.readLine());

        int boards[]= new int[N+1];

        int sum=0;

        for(int i=0;i<N;i++){
            int n = Integer.parseInt(bf.readLine());
            boards[i]=n;
            sum+=n;
        }

        int start=0;
        int last=0;

        int result=0;

        int now=boards[start];

        while(start<=last && last<N){

            int minNow = Integer.min(now,sum-now);

            result = Integer.max(result, minNow);

            if(now == minNow){
                last++;
                now+=boards[last];
            }
            else{
                now-=boards[start];
                start++;
            }

        }

        System.out.println(result);


    }
}