[boj : 20181]꿈틀꿈틀 호석 애벌래 - 효율성

www.acmicpc.net/problem/20181

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

문제 : 만약 www.acmicpc.net/problem/20167 이문제 안푸셨으면 먼저 풀고 오세요. 

전 저번 문제와 같습니다. 다만 n,k의 범위가 엄청 나게 커졌죠.

 

해설 : 이 문제는 www.acmicpc.net/problem/1806 이 문제를 풀수 있으면 충분히 풀 수 있는 문제입니다.

투포인터 + dp 의 개념으로 해결할 수 있습니다.

 

먼저, 원소 하나씩 더해줍니다(r 이 되겠죠). 그리고 만약 더해준 값이 k 이상이 되었을때, 왼쪽부터 하나씩 빼줍니다(l 이 됩니다). 이때 dp 배열을 하나 선언해주고 여기에 최대값이 될 수 있는 값을 저장해 줍니다.

 

dp[i] = "i 번째 애벌래를 먹었을때 가질 수 있는 최대 탈피값" 이 되겠네요.

 

l 과 r 사이에 있는 값들은 현재 계산해야 될 값이 되니, l 이전의 dp값을 가져와 현재 계산한 값과 더해주면 되겠죠.

 

dp[r] = max(dp[r-1],max(dp[r],dp[l] + sum - k))

 

왜 근데 dp[r-1]을 또 비교를 해주는가??

바로 l 이전의 dp 값과 현재 계산해준 값을 더해도 이미 이전 dp 에 저장되어있는 값이 더 클 수도 있기 때문입니다.

(예제, 1 5 4 4 일때 dp[r-1]을 비교해주지 않으면 0 0 3 2 가 되겠죠, 그러나 사실 저 입력값의 최대 탈피값은 2가 아닌 3이 됩니다. 따라서 dp[r-1]을 비교를 해주는 겁니다.)

 

*참고로 오버플로 항상 조심합시다. 저도 매번 이것때문에 엄청 고생하네요....

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

ll sum = 0;
ll arr[100010], dp[100010];

int main()
{
	ll n, k;
	cin >> n >> k;

	for (int i = 1; i <= n; i++)
		cin >> arr[i];

	for (int r = 1, l = 0; r <= n; r++) {
		sum += arr[r];
		dp[r] = dp[r - 1];
		while (sum >= k) {
			dp[r] = max(dp[r], dp[l] + sum - k);
			sum -= arr[++l];
		}
	}
	cout << dp[n];
	return 0;
}