백준 - 2118번 : 두 개의 탑 (C++)

풀이 방법 : 누적 합, 투 포인터

두 지점을 선택해서 해당 지점들 간의 거리의 최댓값을 구하는 문제

시계방향, 반 시계 방향의 거리 둘 중에 작은 값이 거리이다.
시계방향의 거리는 누적 합을 이용해 빠르게 구해줄 수 있고 반 시계방향의 거리는 모든 거리의 총 합에서 시계방향의 거리를 빼주면 구해줄 수 있다.

문제는 두 지점을 어떻게 선택하냐이다. 단순하게 2중 for문을 돌리면 최대 50000 * 50000 번의 반복을 하게 될 것이므로 시간 초과가 될 것이다.

여기서 투 포인터를 활용하면 된다. 시계, 반시계 둘 중에 작은 값이 거리가 되므로 거리의 최댓값은 시계, 반시계 둘 다 거리의 총합의 절반에 가장 가까울 때가 될 것이다.

따라서 시계 방향의 거리와 반 시계방향의 거리를 비교하여 반 시계 방향의 거리가 더 클 경우에는 시계 방향의 거리를 늘리는게 나으므로 오른쪽 인덱스를 증가시키고 그 반대의 경우에는 왼쪽 인덱스를 증가시켜가면서 최댓값을 탐색하면 될 것이다.

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int Dist[50001] = {};

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

	int N;
	cin >> N;
	for (int i = 1; i <= N; ++i)
	{
		cin >> Dist[i];
		Dist[i] += Dist[i - 1];
	}

	int Left = 1;
	int Right = 2;
	int Max = 0;
	while (Left <= Right && Right <= N)
	{
		int ClockWise = Dist[Right] - Dist[Left - 1];
		int AntiClock = Dist[N] - ClockWise;

		int TempDist = min(ClockWise, AntiClock);
		Max = max(TempDist, Max);

		if (ClockWise <= AntiClock)
		{
			++Right;
		}

		else
		{
			++Left;
		}
	}

	cout << Max;
}