[백준] 20167, 20181 꿈틀 꿈틀 호석 애벌레

참고: https://www.acmicpc.net/problem/20167, https://www.acmicpc.net/problem/20181

---

꿈틀꿈틀 호석 애벌레 - 기능성

문제에 주어진 조건이 크지 않으므로 브루트 포스로 해결할 수 있다. 애벌레가 먹이를 먹는 경우와 그렇지 않은 경우로 나눌 수 있고, 만족도가 K 이상일 때 만족도를 0 으로 하고 탈피 에너지를 증가하면 해결할 수 있다.

꿈틀꿈틀 호석 애벌레 - 효율성

동일한 문제로 제한 조건만 달라졌다. 먹이의 개수가 100,000개이며 만족도가 10^8 까지 가능하다. 따라서 브루트 포스로 해결할 수 없다.

일단 특정 구간에서의 누적된 만족도를 구해야하므로 투 포인터(left, right)를 사용하여 누적합을 구할 수 있을 것 같다.

그리고 해당 먹이를 먹는 경우와 그렇지 않응 경우로 나뉘고, 특정 구간에서의 최대 탈피 에너지를 기억해야 하므로 DP를 사용한다.

dp[i] = i 까지의 최대 탈피 에너지

풀이

N = 9, K = 6, 먹이 = [1, 5, 4, 4, 2, 3, 10, 3, 5] 가 주어졌을 때 풀이는 다음과 같다.

0 ~ 1 구간의 누적 만족도는 6으로 탈피 에너지 = 누적 만족도 - K = 0 이다.

0 - 1 구간의 만족도가 6 이상이므로 left를 한 칸 이동 시킨다.

1 - 1 구간의 만족도가 6 미만이므로 right를 한 칸 이동하여 먹이를 먹는다.

1 - 2 구간의 만족도가 9 가 되어 탈피 에너지는 3이 된다.

1 - 2 구간의 만족도가 6 이상이므로 left를 한 칸 이동 시킨다.

2 - 2 구간의 만족도가 6 미만이므로 right를 한 칸 이동하여 먹이를 먹는다.

2 - 3 구간의 만족도가 9 가 되어 탈피 에너지는 2가 된다. 하지만 1 - 2 구간과 2 - 3 구간에서 2번 먹이가 겹치므로 두 구간 중 탈피 에너지가 더 큰 1 - 2 구간을 선택한다. 따라서 dp[3] = 3이 된다.

현재까지 상황은 위와 같다. 이렇게 left, right를 이동하면서 최대 탈피 에너지를 구할 수 있다.

꿈틀꿈틀 호석 애벌레 - 기능성

import java.io.*;
import java.util.StringTokenizer;
public class Main {
    static int N, K, result = 0;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        arr = new int[N];

        st = new StringTokenizer(br.readLine());

        for (int i=0;i<N;i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dfs(0, 0, 0);
        System.out.println(result);
    }
    private static void dfs(int idx, int satisfaction, int energy) {

        if (idx == N) {
            result = Math.max(result, energy);
            return;
        }

        dfs(idx + 1, 0, energy);

        if (satisfaction + arr[idx] >= K) {
            dfs(idx + 1, 0, energy + satisfaction + arr[idx] - K);
        } else {
            dfs(idx + 1, satisfaction + arr[idx], energy);
        }
    }
}

꿈틀꿈틀 호석 애벌레 - 효율성

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];

        st = new StringTokenizer(br.readLine());

        for (int i=0;i<N;i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        long[] dp = new long[N + 1];
        long sum = arr[0]; int left = 0, right = 1;

        while (right <= N) {
            if (sum >= K) {
                while (sum >= K) {
                    dp[right] = Math.max(dp[right], dp[left] + sum - K);
                    sum -= arr[left++];
                }
            } else {
                dp[right] = Math.max(dp[right], dp[right - 1]);

                if (right == N)
                    break;

                sum += arr[right++];
            }
        }

        System.out.println(dp[N]);
    }

}

from sys import stdin
from collections import defaultdict
readline = stdin.readline

N, K = map(int, readline().split())
arr = list(map(int, readline().split()))
dp = defaultdict(int)

def solve():
    left, right, _sum = 0, 0, 0
    while right <= N:
        if _sum >= K:
            while _sum >= K:
                dp[right] = max(dp[right], dp[left] + _sum - K)
                _sum -= arr[left]
                left += 1
        else:
            dp[right] = max(dp[right], dp[right - 1])

            if right == N:
                break

            _sum += arr[right]
            right += 1     


    print(dp[N])

solve()