[백준/BOJ] 백준 20181번 : 꿈틀꿈틀 호석 애벌레 - 효율성

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

20181번: 꿈틀꿈틀 호석 애벌레 - 효율성

vector<long long> cache(100001, 0)을 사용하여 [위치] = 해당 위치에서 끝날 때 최댓값을 업데이트시키는 방법을 이용하였고, 이 과정에서 투 포인터를 이용해서 문제를 해결했다. cache를 업데이트시키는 방법은 cache[right] = max(cache[right], cache[right - 1])를 하고 난 뒤, right를 포함시키면 k이상이 되는 경우 cache[right] = max(cache[right], cache[left - 1] + (sum + value[right]) - k)로 업데이트를 시켜서 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

long long n, k;
vector<long long> value(100001);
vector<long long> cache(100001, 0); //[위치] = 해당 위치에서 끝날때 최댓값

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

	cin >> n >> k;

	for (int i = 1; i <= n; i++)
	{
		long long input;
		cin >> input;

		value[i] = input;
	}

	long long left = 1;
	long long right = 1;
	long long sum = 0;

	while (1)
	{
		if (right > n)
			break;

		cache[right] = max(cache[right], cache[right - 1]);

		//right에서 끝날때 최댓값 계산
		//right를 포함시키면 k이상일때
		if (sum + value[right] >= k)
		{
			cache[right] = max(cache[right], cache[left - 1] + (sum + value[right]) - k);

			if (left < right)
			{
				sum -= value[left];
				left++;
			}

			//값 하나만으로 k를 넘는 경우
			else
			{
				left++;
				right++;
			}
		}

		else
		{
			sum += value[right];
			right++;
		}
	}

	cout << cache[n];

	return 0;
}