[자바, C++] 백준 2118 - 두 개의 탑 (java cpp)

 문제 : boj2118

---

 

필요 알고리즘 개념

• 투 포인터 (두 포인터)
  
  • 두 개의 가상의 포인터를 두고, 그 두 포인터를 적절한 규칙으로 이동시키다보면 효율적으로 답이 나오게 되는 문제이다. 다만 원형 연결을 끼얹은.. 

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  난 개인적으로 문제 지문 자체가 잘 이해가 안되서 해맸었다. 혹시 그런분이 있을 수 있으니 적어보면, 아래처럼 지점 번호는 중요하지 않고 아무튼 지점 N개가 있는데(녹색 원), 간선의 거리가 입력으로 주어진 거리만큼 순서대로 배치되어 있다고 보면 된다.

 

  그리고 임의의 두 정점을 선택하게 되면, 검정색 간선의 합과 주황색 간선의 합이 존재한다. 검정색은 1+2=3, 주황색은 5+4+3=12가 되고 이 중 짧은게 두 지점의 거리라 했으므로 검정색인 3이 거리가 된다. 이 문제에서 찾는건 임의의 두 지점을 선택했을 때 이처럼 양방향 중 짧은게 두 지점의 거리가 되는데, 그 중 가장 큰 거리 값을 찾는거다.

 

---

 

  여기까지 보면 결국 이론적으로 두 탑의 거리의 최댓값은 어느 두 지점에 대해 양방향 거리가 동일한 경우라는걸 예상할 수 있다. 즉, 모든 간선들의 거리합을 양분한 거리가 최댓값이 될 것이다. 만약 모든 정점의 쌍에 대해 거리를 전부 확인할 경우, O(N^2)이 필요할 것이므로 시간초과가 나게 될 것이다.

 

 

  우선 설명의 편의를 위해 지점번호는 내 경우엔 임의로 0부터 N-1로 설정했다 (어차피 문제에 나온 1부터 N까지의 지점번호는 간선에 대한 기준이 제시되지 않았으므로 의미가 없다.). 문제에서 제시된 '예제 입력 1'의 경우 다음처럼 표현 가능하다.

5
1
2
3
4
5

 

 

  내 풀이방법의 경우 우선 두 지점을 나타내는 포인터 역할을 하는 a와 b를 둔다. 그리고 a기준으로 시계방향 거리(주황색)를 sumA, a기준으로 반시계방향 거리(파란색)를 sumB라고 하겠다. 그렇다면 sumA == sumB 일 때가 언제나 최댓값이라 볼 수 있다. a를 기준으로 b를 이동시킨다고 생각해보자. 이 때 sumA < sumB를 기준으로 잡고 b를 움직이다가, 이후 sumA > sumB가 된다면 이미 sumA == sumB인 지점을 지나친 셈이니 다른 기준점을 보는(a를 증가) 방식으로 진행했다.

  

  따라서 규칙은 다음과 같다.

1. sumA == sumB 라면 이후 기준점을 바꾸더라도 그보다 높은 최댓값은 나올 수 없으므로 거기서 종료하면 된다.

2. sumA < sumB 라면 b를 시계방향으로 진행시킨다.

3. sumA > sumB 라면 기준점인 a를 시계방향으로 진행시킨다.

 

  위의 과정을 기준점인 a가 다시 원점으로 되돌아올 때 까지 진행한다. b의 경우엔 값을 증가시킬 때, b++ 이후 b%=n 을 해주면 원형인 것과 관계없이 진행 가능하다. (0->1->...->4->0->1->...)

그럼 최종적으로 a는 최대 O(N)번 이동되고, b도 최대 O(2N)번 이동될 것이므로 O(N+2N) = O(N)으로 수행 가능하다. N^2이 아닌것이, 어차피 a와 b 모두 시계방향으로만 이동하기 때문에 그렇다.

 

 

  이하 예제 입력 1에 대해 a, b의 변화를 순서대로 그려봤다.

 

 

---

 

코드(Java) : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<17);
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            sum += arr[i];
        }
        int a = 0;
        int b = 1;
        int sumA = arr[0];
        int sumB = sum-arr[0];
        int answer = 0;
        while (a<n) {
            answer = Math.max(answer, Math.min(sumA, sumB));
            if (sumA == sumB) {
                System.out.println(answer);
                return;
            } else if (sumA > sumB) {
                sumA-=arr[a];
                sumB+=arr[a];
                a++;
                continue;
            }
            sumA+=arr[b];
            sumB-=arr[b];
            b++;
            b%=n;
        }
        System.out.println(answer);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

---

 

코드(C++) : github

#include <iostream>
using namespace std;

int arr[50001] = {0,};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        sum += arr[i];
    }
    int a = 0;
    int b = 1;
    int sumA = arr[0];
    int sumB = sum-arr[0];
    int answer = 0;
    while (a<n) {
        answer = max(answer, min(sumA, sumB));
        if (sumA >= sumB) {
            sumA-=arr[a];
            sumB+=arr[a];
            a++;
            continue;
        }
        sumA+=arr[b];
        sumB-=arr[b];
        b++;
        b%=n;
    }
    cout << answer;
    return 0;
}