2118 - 두 개의 탑

문제

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

느낀점

투 포인터를 응용하는 문제였는데, 괜히 정렬하면서 문제 마음대로 해석했다가 틀렸다.. 문제를 똑바로 읽자..

풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define pii pair<int, int>

int main()
{
    int N;
    cin >> N;
    vector<pii> distance;
    distance.push_back(make_pair(0, 0));
    long long totalDistance = 0;
    for (int i = 0; i < N; i++)
    {
        int temp;
        cin >> temp;
        totalDistance += temp;
        distance.push_back(make_pair(i + 1, temp));
    }

    int left = 0;
    long long answer = 0;
    long long base = distance[left].second;
    for (int right = 1; right < N + 1; right++)
    {
        base += distance[right].second;
        long long comp = totalDistance - base;
        answer = max(answer, min(base, comp));
        if (base < comp)
        {
            continue;
        }
        else
        {
            while (true)
            {
                base -= distance[left++].second;
                long long comp = totalDistance - base;
                answer = max(answer, min(base, comp));
                if (base < comp)
                {
                    break;
                }
            }
        }
    }
    cout << answer;

    // 0 1 2 3 4 5
    // 1 14 / 3 12 / 5 10 / 6 9 / 10 5 / 9 6 / 7 8 / 12 3 / 9 6

    // 5 10 15
    // 5 25 / 10 20 / 15 15 

    return 0;
}