[백준/JAVA] 2118번: 두 개의 탑

📖 문제

https://www.acmicpc.net/problem/2118

 

 

 

💡  풀이 방식

• 누적합, 투 포인터

 

N가지 지점 中 2가지를 뽑는 경우의 수는 N * (N-1)/2이고, 이러면 약 12억 5천만을 넘으므로 시간 초과가 발생한다.

그러므로 투 포인터로 두 지점을 뽑는다.

 

그리고 나서 정방향 / 역방향으로 진행하며 최대 거리를 구한다.

 

 

 

🔺 코드

import java.util.*;
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[] arr = new int[N+1];
 
        int sum = 0;    // 누적합
        
        for(int i = 0 ; i < N ; i++) {
            int dist = Integer.parseInt(br.readLine());
            arr[i] = dist;
            sum += dist;    // 누적합 갱신
        }
        
        int start = 0;
        int end = 0;
        
        int result = 0;
        int now = arr[start];
        
        while(start <= end && end < N) {
            int minNow = Integer.min(now, sum-now);
            
            result = Integer.max(result,minNow); // 최대 거리 업데이트
            
            if(now == minNow) { // 종료점 이동하며 최적의 위치 탐
                end++;
                now += arr[end];
            }
            else { // 시작점 이동하며 거리 갱신
                now -= arr[start];
                start++;
            }
        }
        
        System.out.println(result);
    }
}
 

 

 

 

➕ 다른 풀이 방식

- 언어는 다르지만 개인적으로는 이 풀이가 더 이해하기 좋은 듯 하다..

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

 

 

---

💦 어려웠던 점

- 문제 자체를 이해하지 못 했다,,,🫠🫠

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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

 

백준 2118 두 개의 탑 (JAVA 자바 풀이)