백준 2118 두 개의 탑 [c++]

21 Jun 2022 in Develop / Solving

c++

문제 분석

• 1부터 N까지의 지점이 있으며, 원형으로 연결되어 있다.
• 두 지점에 탑을 세울건데, 두 탑 사이의 거리가 최대가 되어야 한다.
• 탑 사이의 거리는 원형의 라인을 따라 갈 때, 두 길이 중 작은 것으로 한다.

입력조건

지점의 개수 N
N줄에 걸쳐 {
	두 지점을 잇는 거리 a
}

풀이과정

• 부분합이 두개인 투포인터.
• 지점의 개수가 무조건 2개 이상인 것이 중요하다.
  • 애초에 한개면 말이 안되긴 하지만,,
• 두 개의 포인터를 0, 1에 우선 배치한다.

• 이러면 0번 거리가 거리1이 되고, 나머지를 다 더한 것이 거리2가 된다.

• 거리1, 거리2를 비교해서 더 작은 값을 초기 답으로 지정해 놓는다.
• 투 포인터 반복
  • 거리1, 거리2를 비교해서
    • 거리1 < 거리2이면
      오른쪽 포인터를 옮겨서 거리1을 늘림
    • 거리1 > 거리2이면
      왼쪽 포인터를 옮겨서 거리2를 늘림
    • 거리1 == 거리2이면
      두 거리 중 아무거나 출력하고 프로그램 종료
      • 이게 중요한데, 거리1 + 거리2 가 항상 일정하기 때문에,
        거리1 == 거리2 이면 무조건 가능한 최댓값이 될 수 밖에 없음.

전체 코드

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    int arr[n];
    int sum2 = 0;
    // 두 탑의 거리의 최댓값.
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
        sum2 += arr[i];
    }

    int l = 0;
    int r = 1;
    int sum1 = arr[0];
    sum2 -= sum1;

    int ans = min(sum1, sum2);
    while(r < n) {
        // sum1을 올리기
        if(sum1 == sum2) {
            cout << sum1;
            return 0;
        }
        if( sum1 < sum2 || l == r) {
            sum1 += arr[r];
            sum2 -= arr[r];
            r++;
        }
        // sum2를 올리기(l 증가)
        else {
            sum1 -= arr[l];
            sum2 += arr[l];
            l++;
        }
        
        // 최댓값 넣기.
        ans = max(ans, min(sum1, sum2));
    }
    cout << ans;
}