📙[Algo] 24.07.18 알고리즘

알고리즘 문제) BOJ 13398. 연속합 2

• 링크 : https://www.acmicpc.net/problem/13398

문제 요약

• n개의 정수로 이루어진 임의의 수열
• 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다
  • 수는 한 개 이상 선택해야 한다
  • 수열에서 수를 하나 제거할 수 있다

시간 제한

• 2초

입력

• 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고
• 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다
  • 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수

출력

• 첫째 줄에 답을 출력

접근법

• 부분 연속 수열의 합 중 가장 큰 값을 구하는 문제
  • 이때, 중간에 하나 제거가 가능함
• 매개변수 start, end를 통해 부분 연속 수열이 시작됐는지, 끝나는지 체크하도록 했다
  • 0 : 시작X or 끝X
  • 1 ; 시작O or 끝o
• 또한, remian변수를 통해 연속 수열 중간에 수를 제거했는지 여부를 체크했다
  • 1 : 아직 제거 X
• 만약 end가 0일 경우, 아직 부분 수열이 끝나지 않았으므로 현재 수를 더해주는 재귀 호출이 가능하게 했다.
• 또한, start가 1인 경우,
  • 이미 연속 부분 수열이 시작 되었으므로, 중간에 수를 건너 뛰는 경우는 아래 2가지가 존재
    • 중간 숫자 하나만 제거 (remain > 0)
    • 또는, 현재 부분 수열을 끝내 버리는 경우
• start가 0인 경우에는 아직 부분 수열을 시작하지 않았으므로, 현재 수를 패스하는 재귀 호출이 가능하게 했다.
• 마지막으로 전체 수를 순회 했을 때,
  • start가 0일 경우 아예 선택을 안 한 경우이므로 가지 치기했고, (가장 작은 순 반환)
  • 그게 아닐 경우 return 0을 했다.
• 결국 dp[cur][start][end][remain] 에는 현재 상태에서의 최대합이 담겨지도록 했다.

코드

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


public class Main {
    static int N;
    static int[] arr;
    static int[][][][] dp;

    static int recur(int cur, int start, int end, int remain) {

        if (cur == N) {
            if (start == 0) return Integer.MIN_VALUE;
            else return 0;
        }

        if (dp[cur][start][end][remain] != -1) return dp[cur][start][end][remain];

        int ret = Integer.MIN_VALUE;

        // 현재 수 합하기 + 연속합 시작 -> start = 1
        // 연속합이 끝나지 않았다면
        if (end == 0) ret = Math.max(ret, recur(cur + 1, 1, end, remain) + arr[cur]);

        // 현재 수 건너뛰기
        if (start > 0) {
            if (remain > 0) {
                // 중간에 한 번 건너 뛸 수 있음
                ret = Math.max(ret, recur(cur + 1, start, end, remain - 1));
            } else {
                // 이미 건너 뛴 경우 -> 아예 종료
                ret = Math.max(ret, recur(cur + 1, start, 1, remain));
            }
        } else {
            // 아직 시작하지 않았다면 건너뛰기 가능
            ret = Math.max(ret, recur(cur + 1, start, end, remain));
        }

        dp[cur][start][end][remain] = ret;
        return ret;
    }

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

        N = Integer.parseInt(br.readLine());

        arr = new int[N];

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

        dp = new int[100010][2][2][2];
        for (int[][][] d : dp) {
            for (int[][] d2 : d) {
                for (int[] d3 : d2) {
                    Arrays.fill(d3, -1);
                }
            }
        }

        int ans = recur(0, 0, 0, 1);

        System.out.println(ans);
    }
}