BOJ : 백준 2118 두 개의 탑

문제

문제
1번부터 N번까지의 지점이 있다. 각각의 지점들은 차례로, 그리고 원형으로 연결되어 있다. 이 지점들 중 두 곳에 두 개의 탑을 세우려고 하는데, 두 탑의 거리가 최대가 되도록 만들려고 한다.
지점들이 원형으로 연결되어 있기 때문에, 두 지점 사이에는 시계방향과 반시계방향의 두 경로가 존재한다. 두 지점 사이의 거리를 잴 때에는, 이러한 값들 중에서 더 작은 값을 거리로 한다.
연결되어 있는 두 지점 사이의 거리가 주어졌을 때, 두 탑의 거리의 최댓값을 계산하는 프로그램을 작성하시오.

입력
N
두 지점 사이의 거리(N회만큼)

풀이

탑 사이의 길이를 구하는 건 어렵지 않은데 답으로 삼을 기준을 찾는 점을 생각해내는 게 힘들었다.

문제를 읽어보면, 두 탑 사이의 거리로 최댓값을 구하지만 진짜 real 최댓값을 구해서는 안 된다. 예제만 보아도 5, 1, 2 / 3, 4 => 8 / 7 해서 7이 답이다.

Math.max로 반대 경로 최대 값을 구해버리면 1/ 5,4,3,2 가 될 것 같아서.. 최대값 말고 시계 방향, 반대 방향 경로 서로의 값이 제일 비슷한 걸 찾으면 될 것 같다. Math.abs(dist1-dist2)를 통해 절대값을 구하고, 값이 제일 적은 쌍 중 더 작은 수!
이렇게 생각해본 결과... 플로우는 다음과 같다.

누적합을 통해 n~m까지의 거리를 구한다.
전체 합 - n~m까지의 거리를 구하여 반대 방향의 경로 길이를 구한다.
Math.abs(n~m 거리 - 반대 방향의 경로 길이)로 min을 구한다.
min으로 정해진 값 쌍 중 더 작은 수를 print

누적합(Prefix Sum)은 n~m까지의 원소들의 합을 구하는 데 탁월한 알고리즘이다. 누적합용 수열에 시작점(첫 번째 원소)부터 끝까지 쭉 합한 값을 넣어 만든다.

n~m 사이의 값을 찾고 싶다면 누적합수열[m] - 누적합수열[n-1]로 구하면 된다.

import java.io.*;

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 distances[] = new int[N];
		int prefixSum[] = new int[N];
		prefixSum[0] = 0;
		
		for(int i=0; i<N; i++) {
			distances[i] = Integer.parseInt(br.readLine());
			if(i == 0) {
				prefixSum[i] = distances[i];
			} else {
				prefixSum[i] = prefixSum[i-1] + distances[i];
			}
		}
		
		int start = 0, end = 1;
		int min = Integer.MAX_VALUE;
		int res = 0;
		while(start < N-1) {
			int route = prefixSum[end] - prefixSum[start];
			
			if(Math.abs(route-(prefixSum[N-1]-route)) < min) {
				min = Math.abs(route-(prefixSum[N-1]-route));
				res = Math.min(route, prefixSum[N-1]-route);
			}
			
			end++;
			if(end == N) {
				start++;
				end = start + 1;
			}
		}
		
		System.out.println(res);
		
				
	}

}

3
1 2 3 999
처럼 1,2,3 / 999로 나눠야 하는 문제가 있을 수도 있으므로 모든 순서쌍을 다 돌아야 한다고 생각했다. 그래서 start = 0; end = start+1;로 시작하여, end를 하나씩 추가해가며 모든 순서쌍을 돌되, end++했을 때 end==N이면 start++, end = start + 1을 해주었다.

중간에 한 번 틀렸는데, if(Math.abs(route-(prefixSum[N-1]-route)) < min) 부분을 if(Math.abs(prefixSum[N-1]-route))로 작성했었다... 찾는데 생각보다 조금 시간이 오래 소요됐다...😭😭😭😭

문제를 풀며

중간에 별 거 아닌 걸로 한 번 틀리고 + 이유를 찾는데 시간을 꽤 소요한 게 아쉽다... 코드를 너무 가독성 떨어지게 작성하는 것 같아 앞으로는 알고리즘 문제를 풀 때 가독성도 고려하여 작성해야겠다.

다른 분들의 풀이들을 보니 엄청 간결하게 작성해서 놀랐다. 복잡하게 생각한 것 같다...
다른 풀이 방법은 아래와 같다.

시계, 반시계 중 더 짧은 경로를 선택, 그 중 최대값을 출력해야 한다.

점A 고정, 점B을 늘려가며 노드를 선택.(= 시계 방향 경로)
만약 현재 경로(시계) >= 반대 경로(반시계)인 경우, 점B을 움직여 시계 방향 거리를 줄인다.
B 고정 이후 A가 한 번씩 옮겨가며 비교를 계속 == 두 포인터가 최대 한 바퀴를 돌며 이동(O(n))
시계 방향 경로가 작을 때 점B를 움직이면 시계 방향 경로가 커짐.
시계 방향 경로가 클 때 점A를 움직이면 반시계 방향 경로가 커짐.

이렇게 균형을 맞춰 답을 출력하는 방법이었다. 비슷한 문제가 있으면 이 풀이를 떠올려 풀어봐야지.

문제