문제 이해

N개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어간다.

애벌레는 0위치에서 N방향으로 이동하는데, 매초 1만큼 무조건 오른쪽으로 이동한다.

애벌레는 먹이를 한 번 먹으면 연속으로 먹는데, 최소 만족도 K 이상이 되거나 더 이상 먹을 먹이가 없을 경우(즉 나뭇가지 끝에 다다를 경우) 연속적으로 먹는 것을 멈춘다.
만약 최소 만족도 K 이상이 되면 K를 초과한 만족도만큼 "탈피 에너지"를 획득하고, 만족도는 다시 0이 되며 다음 먹이부터 다시 먹을 수 있게 된다.

애벌레는 먹이를 먹거나 지나칠 수 있을 때 탈피 에너지가 최대가 되도록 먹이를 먹으려고 한다.
이 때 탈피 에너지의 최댓값을 구하는 문제이다.

---

문제 풀이

DP를 통해 해결할 수 있는 문제이다.

문제는 DP에 어떤 값을 저장할 것인가에 대한 문제이다.
나는 DP[K]를 0 ~ K 미만까지의 먹이만 존재할 때의 최대 탈피 에너지로 구했다.

투 포인터도 동시에 활용했는데, left와 right를 활용했다.
right는 DP[K]를 구할 때 K값으로 설정하였고, left는 먹이를 먹기 시작한 시점으로 결정하였다.
즉, 애벌레가 마지막으로 먹는 먹이는 left ~ right까지의 먹이를 먹게 되는 것이다.
그리고 left ~ right까지 먹은 먹이 값을 sum으로 저장했다.

만약 sum < K라면 먹이를 더 먹어야 한다.
먼저 dp[right]는 dp[right]과 dp[right-1] 중 큰 값으로 설정할 수 있을 것이다.
또한 sum은 K 미만이므로 K 이상이 될 때 까지 먹이를 먹어야 하기 때문에 arr[right]값을 더해준다.

sum >= K인 상황이 중요하다.
left ~ right(미만)까지의 먹이를 먹은 상황이다.
dp[left]에는 left 미만까지의 먹이를 먹었을 때 최대 탈피 에너지가 저장되어 있을 것이다.
따라서 dp[right]는 dp[right]과 dp[left] + {sum(left ~ right까지 먹은 먹이) - K} 중 큰 값으로 저장 될 것이다.
그리고 left ~ right까지의 합이 K 미만이 될 때 까지 left를 1씩 증가시키면서 최대한 모든 경우의 수를 다 구해서 이 중 최댓값으로 dp[right]를 설정해주면 되는 것이다.

우리는 0 ~ (N-1)까지의 먹이가 주어졌을 때의 상황을 보고 싶은 것이므로 dp[N]에 저장된 값을 출력하면 된다

---

코드

import java.io.*;
import java.util.*;


public class Main {
	static StringBuilder sb = new StringBuilder();
	static int answer = 0;
	
	static int N, K;
	static int[] arr;
	
	public static void main(String[] args) {
		
		FastReader sc = new FastReader();
	
		N = sc.nextInt();
		K = sc.nextInt();
		
		arr = new int[N];
		
		for(int i =0;i<N;i++) {
			arr[i] = sc.nextInt();
		}
		
		int left = 0;
		int right = 1;
		int sum = arr[left];
        // left이상 right "미만"의 먹이 합이 sum에 저장되기 때문에 right = 1
		
		long[] dp = new long[N+1];
        // dp[K] : 0 ~ (K-1)번째 먹이가 주어진 상황에서 최대 탈피 에너지
		
		while(right<=N) {
        
			if(sum>=K) {
                while (sum >= K) {
                // sum < K가 될 때 까지 left를 1씩 증가시키기
                
                    dp[right] = Math.max(dp[right], dp[left] + sum - K);

                    sum -= arr[left];
                    left++;
                }
			}
			else {
            // sum < K이므로 arr[right] 음식을 먹여야 한다.
                dp[right] = Math.max(dp[right], dp[right - 1]);

                if (right == N)
                    break;

                sum += arr[right];
                right++;
			}
		}
		
		System.out.println(dp[N]);
	}
	
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과