[BOJ20181] 꿈틀꿈틀 호석 애벌레 (DP, 투포인터)

 

---

메모리 초과의 경우 
- 재귀 호출로 인한 스택 오버 플로우 발생할 경우 종료 조건 확인
- 변수 타입이 범위 초과할 경우 (long인데 int로 선언하거나) 

시간 초과의 경우 (1초에 1억번 연산을 가정했을때)
- 시간 복잡도가 적철지 못한 문제 풀이 했을 때 
- 주어진 query에 대한 결과나, 조합에 대한 결과를 구할 때 전처리 후 사용하기

결과 값을 구해지는데 실패가 케이스가 뜨는 경우 
- 변수 타입, 최대치, 초기화 확인

 

문제 링크

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

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

 

문제 풀이 

- 처음 투포인터로 문제를 풀었으나, 5/39 라는 처참한 결과를 확인

- 풀이 방법을 찾아본 결과 "DP + 투포인터", "투포인터" 방식 두 개가 있었고 참고하여 둘다 풀이 함

- 시간 복잡도 : 둘다 O(N)

 

1) 투포인터 + DP

- K = 6인 경우 투포인터(L, R)로 이동하면서 K를 만족하는 경우를 찾는다. 

- 시작점(L)과 탈피 에너지(sum - k) 를 기록 => infos[R].add(new Info(L, 탈피 에너지)

- 투포인터 종료 후 1~N 순차 조회하면 DP 테이블을 갱신한다

-  1 ~ N 까지 포인터 이동하면서, (시작점, 탈피 에너지)에 대한 기록이 있는 경우 반복 조회하면서 최대값으로 갱신한다

DP[N] = DP[N - 1] // 이전 인덱스까지의 최대값
for(...) DP[N] = max(DP[N], DP[start - 1] + 에너지) 

 

7번 인덱스(10) 을 살펴보면 아래와 같다 

앞선 최대 탈피 에너지와 범위내의 탈피 에너지의 합을 비교하며 최대값을 DP 테이블에 갱신한다

DP[N]에 최대 탈피 에너지가 구해짐, O(N)

 

2) 투포인터 

- 마찬가지로 O(N)만큼 시간복잡도가 소요된다

- 임시 필드 선언해서 최대 탈피 에너지를 기록하여 사용한다

- 결과값을 순차 조회하면서 최대값을 비교하여 구한다 ( N번 인덱스에 최대값이 없을 수 있음 ) 

 

제출 코드 

1) 투 포인터 + DP 풀이

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

public class Main {
    
    static int n, k;
    static int[] foods;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        foods = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            foods[i] = Integer.parseInt(st.nextToken());
        }
    }

    static class Info {
        private int start;
        private int point;

        public Info(int start, int point) {
            this.start = start;
            this.point = point;
        }

        public int start() { return this.start; }
        public int point() { return this.point; }
    }

    static void dp() {
        List<Info>[] infos = new ArrayList[n + 1];
        for(int i = 1; i <= n; i++) infos[i] = new ArrayList<>();

        int sum = 0;
        for(int L = 1, R = 0; L <= n; L++) {
            while(sum < k && R + 1 <= n) {
                R += 1;
                sum += foods[R];
            }

            if(k <= sum) {
                infos[R].add(new Info(L, sum - k)); // (시작점, 탈피에너지)
            }

            sum -= foods[L];
        }

        long[] dp = new long[n + 1];
        for(int R = 1; R <= n; R++) { 
            // 조건문으로 isEmpty() 필터링할 경우 틀림
            dp[R] = dp[R - 1];
            for(Info i : infos[R]) {
                dp[R] = Math.max(dp[R], dp[i.start - 1] + i.point);
            }
        }

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

    static void pro() {
        dp();
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}

 

2) 투 포인터 풀이

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

public class Main {
    
    static int N;
    static long K;
    static int[] foods;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // 먹이 개수
        K = Long.parseLong(st.nextToken()); // 최소 만족도

        foods = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= N; i++) {
            foods[i] = Integer.parseInt(st.nextToken());
        }
    }

    static void twoPointer() {

        long[] _dp = new long[N + 1];

        int R = 0;
        long maxEnergy = 0;
        int sum = 0;
        for(int L = 1; L <= N; L++) {
            maxEnergy = Math.max(maxEnergy, _dp[L - 1]);

            while(sum < K && R + 1 <= N) {
                R += 1;
                sum += foods[R];
            }

            if(sum >= K) {
                _dp[R] = Math.max(_dp[R], maxEnergy + (sum - K));
            }

            sum -= foods[L];
        }

        long ans = 0;
        for(int i = 1; i<= N; i++) ans = Math.max(ans, _dp[i]);

        
        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        input();
        twoPointer();
    }
    
}