2118 두 개의 탑 (Java)

두 개의 탑

문제

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

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

풀이

우선 두 지점사이의 거리를 구하는 알고리즘은 모든 두개의 점에 대해서 계산하면 된다.
이를 단순하게 구현하면 O(N^2)의 시간복잡도를 가지므로 N의 범위가 클 때 시간초과가 발생한다.

이 문제에서 1번에서 3번으로 가는 경로는 1 -> 2 -> 3으로 가거나 그 반대방향으로 가는 것이 전부이다.
이렇게 무조건 경로를 거쳐 간다면 누적합을 이용해 구현할 수 있다.

for (int i = 1; i <= n; i++) {
            forward[i] += forward[i - 1];
        }

위와 같이 구현한다면 1 - n번까지의 누적합을 구할 수 있다.
이때 n의 값은 한바퀴를 다 돌아 자신까지 왔을때의 값이다.
n이 증가하는 순이 시계방향이라 가정한다면 반시계 방향은 forward[n](한바퀴 다 돌았을 때의 거리) - 어느 지점까지의 거리(ex. 1~3의 거리 : forward[3] - forward[1])로 쉽게 구할 수 있다.
이를 활용해서 구현하면 된다.

코드

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

public class Main{

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] forward = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            forward[i] = Integer.parseInt(br.readLine());
        }

        for (int i = 1; i <= n; i++) {
            forward[i] += forward[i - 1];
        }

        int ans = 0;

        // start point
        for (int i = 0; i < n; i++) {
            // end point
            for (int j = i + 1; j < n; j++) {

                //시계방향
                int forDist = Math.abs(forward[j] - forward[i]);
                // 반시계
                int revDist = forward[n] - forDist;

                int dist = Math.min(forDist, revDist);

                ans = Math.max(ans,dist);
            }
        }
        System.out.println(ans);

    }
}