[C++][백준] 꿈틀꿈틀 호석 애벌레 - 효율성(20181) - 투포인터, DP

문제

꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 수 있다. 또한 매초 1 만큼 오른쪽으로 무조건 진행한다.

호석 애벌레는 i 번째 먹이가 맛있을수록 높은 만족도를 얻는다. 호석 애벌레는 절제라는 것을 모르는 욕심쟁이기 때문에 한번 먹이를 먹기 시작하면 연속적으로 계속 먹어야 하며, 누적된 만족도가 최소 만족도 K  이상이 되거나 더 이상 먹을 먹이가 없을 때에 연속적으로 먹는 것을 멈춘다. 만약 최소 만족도 이상이 되면 K 를 초과한 만족도만큼 탈피 에너지를 축적한다. 직후에 호석 애벌레의 만족도는 다시 0 이 되고 먹이를 먹을 수 있게 된다. 나뭇가지를 전부 통과했을 때에 소화를 다 못 했을 경우에도 탈피 에너지는 최소 만족도를 넘기는 순간 이미 축적한 것으로 생각하자

 

예를 들어 위와 같이 9개의 먹이가 존재하면, 호석 애벌레는 미래를 도모하여 1번 먹이를 과감하게 포기한다. 그리고 2번부터 먹기 시작해서 3번까지 먹으면 만족도가 9가 되어 3의 에너지를 축적하게 된다. 같은 이유로 4번 먹이도 포기하고 5번부터 먹으면 7번까지 연속으로 먹어서 15의 만족도를 얻는다. 이를 통해 9의 탈피 에너지가 쌓인다. 8, 9번 먹이까지 먹게 되면 2의 탈피 에너지가 축적된다. 이렇게 얻은 총 14의 탈피 에너지가 위의 예제에서는 최대치이다.

매초마다 호석 애벌레는 오른쪽으로 이동하면서 먹이를 지나치거나 먹기 시작할 수 있다. 먹기 시작하면 만족도가 채워질때까지 먹게 될것이다. 어떤 먹이들을 대해 먹어야 축적된 탈피 에너지가 최대가 될 수 있을까?

입력

첫번째 줄에 먹이 개수 N, 최소 만족도 K 가 공백으로 주어진다.

두번째 줄에는 1 번부터 N 번 먹이의 만족도가 순서대로 주어진다.

 

출력

축적된 탈피 에너지의 최댓값을 구하라. 만약 탈피를 한 번도 할 수 없다면 0을 출력한다.

 

풀이

DP 와 투포인터를 사용해야하는 문제입니다. 

먹이를 한번 먹기 시작하면 만족도 K가 채워질때까지 연속으로 먹게됩니다.

먹이를 그냥 지나칠지 먹을지 선택할 수 있습니다.

 

자연수가 주어지고, 연속적인 합이 특정 조건을 만족해야 할 때 투포인터 알고리즘을 떠올릴 수 있습니다.

고를지 말지 먹을지 말지 선택하는 문제는 DP를 떠올릴 수 있습니다.

dp 배열에 기록된 값 dp[idx]는 idx 위치까지 최선을 다했을 때 얻을 수 있는 점수라고 가정합니다.

 

 

이전에 풀이했던 투포인터 알고리즘으로 풀이한 부분합 문제를 참고하면 도움이 됩니다.

vanilla-sue.tistory.com/49

[C++][백준] 부분 합(1806)

해당 문제는 부분합이 S 이상일 때 가장 짧은 부분합의 길이를 찾는 문제였습니다.

부분합이 S 미만이라면 포인터 e를 증가시켜주고, 

부분합이 S 이상이라면 길이를 갱신해준 뒤, 포인터 s를 증가시켜줍니다. 

 

애벌레 문제도 마찬가지로 

부분합이 K 미만이면 포인터 e를 증가시켜주고,

부분합이 K 이상이라면 dp 배열을 갱신해준 뒤, 포인터 s를 증가시켜줍니다.

 

저는 부분합을 [s, e)로 정의하였습니다. 

따라서 s와 e가 동일한 경우 아무것도 포함하지 않은 부분집합이 됩니다.

 

이때 dp는 (dp[s - 1] + 현재 부분합에서 얻은 점수) vs dp[e - 2] vs dp[e - 1]로 갱신됩니다. 

 

케이스 하나 하나 살펴보도록 하겠습니다.

 

1. dp[s - 1] + 현재 부분합에서 얻은 점수

e의 idx가 5일 때 [s, e)는 9이므로 K보다 크기 때문에 점수 계산을 해야합니다.

계산한 점수를 dp[4]에 기록할 것입니다. 

 

이때 dp[s - 1]인 dp[2]는 현재 부분합 이전 최선을 다해서 먹이를 먹었을 때 얻었던 점수가 기록 되어있습니다.

dp[2] + (9 - K) 계산 결과인 6은 dp[e - 2]인 dp[3]보다 크기 때문에 6으로 dp 값을 갱신합니다. 

 

 

2. dp[e - 2] 

e의 idx가 5일 때 [s, e)는 7이므로 K보다 크기 때문에 점수 계산을 해야합니다.

계산한 점수를 dp[4]에 기록할 것입니다. 

 

dp[3]은 내 이전까지 최선을 다해서 먹이를 먹었을 때 얻었던 점수가 기록 되어있습니다.

dp[3]인 3은 dp[s - 1] + 현재 부분합인 2보다 크기 때문에 3으로 dp 값을 갱신합니다. 

 

즉 노란 동그라미 두개를 합친것보다 빨간 동그라미 점수가 크다는 의미입니다.

 

2. dp[e - 1] 

 

[s, e) 값 15는 K보다 크기 때문에 점수를 계산하여 dp[3]을 갱신하였습니다.

갱신 후 s를 증가시킵니다.

 

[s, e) 값 8은 K보다 크기 때문에 점수를 계산하여 dp[3]을 갱신하려고 합니다.

이때 이전에 갱신한 dp[3] 값이 더 크지만 현재 계산 값 8로 값을 덮어쓰고있습니다.

이와 같은 상황을 막기위해 dp[e-1]도 비교합니다.

 

전체 코드는 아래와 같습니다.

#include <iostream>

using namespace std;

int N, K;
long long arr[100010];
long long dp[100010];

int max(long a, long b) {
	if (a > b) return a;
	else return b;
}

int main() {
	cin >> N >> K;

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

	int s = 1, e = 1;
	long long tmp = 0;
	dp[s] = 0;

	while (true) {
		if (tmp < K) {
			tmp += arr[e];
			dp[e] = dp[e - 1];
			e++;
		}
		else {
			int curSubSum = tmp - K; // 현재 부분합의 score
			dp[e - 1] = max(max(dp[e - 1], dp[e - 2]), dp[s - 1] + curSubSum);

			tmp -= arr[s];
			s++;
		}

		if (e > N + 1) {
			break;
		}
	}

	cout << dp[N];

	return 0;
}