[Gold 2] 20181 꿈틀꿈틀 호석 애벌레 - 효율성

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

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

 

이 문제는 투 포인터를 사용한 DP 문제이다.

문제에서 각 먹이의 만족도의 최대값이 100000000이고, 먹이의 최대수가 100000이다.

따라서 각 먹이의 만족도의 합의 최대 값은 10^8 * 10^5 = 10^13이 된다. 

이는 int의 범위인 10^9를 벗어나기 때문에  DP는 long long 형을 사용해야한다.

 

문제에서 투 포인터를 사용한 이유는 호석 애벌레가 미래를 도모하기 때문이다.

미래를 도모할 수 있는 방법은 투 포인터이며 이를 활용해 과거의 만족도가 미래의 만족도보다 작으면 미래의 만족도를 사용하면된다.

 

위에서 생각한대로 문제를 다시 본다면 점화식을 아래와 같이 새워볼 수 있다.

• 현재 합이 최소 만족도(K)보다 큰 경우
  • start 포인터가 가리키는 이전 대상이 더 크다면 축적 대상으로 변경
  • DP[end 포인터 - 1] = MAX(DP[end 포인터 - 1], 축적 대상 + 누적합 - K)
  • 위 점화식은 start 포인터 이전까지 탈피 E의 최대 값을 찾아 sum−k와 더해 끝점인 DP[end -1] 값을 갱신해주는 과정이다.
  • start를 한 칸 옮겨 새로운 구간을 찾을 수 있다.
• 현재 합이 최소 만족도(K)보다 작은 경우
  • end 포인터가 가리키는 만족도를 누적한다.

 

#include<iostream>
using namespace std;
 
int N, K;
long long sum, dp[100001], temp, ans;
int arr[100001];
 
int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);
 
	cin >> N >> K;

	for (int i = 0;i<N;i++) 
        cin >> arr[i];

    int start = 0, end = 0;

	while (end <= N) {
		if (sum >= K) {
			temp = (start == 0 ? 0 : max(temp, dp[start - 1]));
			dp[end - 1] = max(dp[end - 1], temp + sum - K);
			sum -= arr[start++];
		}
		else sum += arr[end++];
	}

	for (int i = 0; i < N; i++)
		ans = max(ans, dp[i]);

	cout << ans<<'\n';
}