[백준 13398] 연속합2

문제

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

13398번: 연속합 2

 

문제 이해

백준의 연속합2 문제입니다.

n개의 임의의 수열이 주어졌을 때, 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 가장 큰 합을 구하는 문제입니다. 다만, 연속합 문제와는 다르게 수열에서 수를 하나 제거할 수도 안 할 수도 있다는 조건이 있습니다.

n이 1이상 100,000 이하라는 점에서 시간 복잡도 O(N) 안에 풀어야 한다고 생각했고 다이나믹 프로그래밍(Dynamic Programming)을 이용했습니다.

 

풀이

 

①

먼저 수열에서 1개의 수를 제거할 수 있는 조건이 없다고 생각해 봅니다.

그렇다면 n번째 index를 마지막 원소로 가지는 수열의 연속합을 dp[n]이라 하면,

자기 자신을 원소로 가질 때 최댓값인 경우:

dp[n] = a[n]

n-1번째 index를 마지막 원소로 가지는 수열의 연속합에 현재 자신의 수를 합할 때 최댓값인 경우:

dp[n] = dp[n-1]+a[n]

dp[n]은 위 2가지 경우로 구성되기 때문에, dp[n] = Math.max(a[n], dp[n-1]+a[n]) 이라는 점화식을 도출할 수 있습니다. 즉, i가 1부터 n까지 증가하면서 (수열에서의 자신의 index 수) 와 (자신의 이전 index까지의 연속합과 자신의 수를 더한값)을 비교하면서 최댓값을 갱신해주면 됩니다.

 

②

이제 수열에서 1개의 수를 제거할 수 있는 조건을 추가해보겠습니다.

임의의 수열이 1 2 3 4 5 6 이라고 주어졌을 때, 4라는 숫자를 뺀 연속합의 최댓값은 3을 마지막 원소로 가지는 수열의 연속합과 5를 시작 원소로 가지는 수열의 연속합을 더하면 됩니다.

 

①번에서 구한 dp배열을 left 배열로 바꾸면, left[n]은 n번 index의 숫자를 마지막 원소로 가지는 수열의 연속합을 나타냅니다. right배열을 새로 만들어 주면, right[n]은 n번 index의 숫자를 시작 원소로 가지는 수열의 연속합을 나타냅니다. 이 2개의 배열을 통해 위 문제를 해결할 수 있습니다.

 

③

②에서 말한 문제풀이 개념을 정리하면

i) i는 1부터 n까지 증가하면서 left[i] = Math.max(a[i], left[i-1]+a[i])

ii) i는 n부터 1까지 감소하면서 right[i] = Math.max(a[i], right[i-1]+a[i])

iii) ans = Math.max(ans, left[i-1]+right[i+1])

i)에서 ans(출력값)의 최댓값을 갱신하면서 구해주면 백준의 연속합 문제의 정답을 구할 수 있습니다. 여기에 ii)에서 구한 right배열을 활용하면 iii)에서 전체 수열에서 하나씩 수를 제거해보면서 ans값을 갱신하여 연속합2 문제의 정답을 구할 수 있습니다.

 

+

초기에 n을 입력받은 후, a[n+2]배열을 선언하였습니다. 그 이유는 입력으로 주어지는 수열을 a[1]~a[n]에 집어넣고 a[0]와 a[n+1]은 for문에 Index Error를 방지하기 위한 조건을 걸어주지 않기 위해 만들었습니다.

 

소스 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
    static int n, ans;
    static int[] a, right, left;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine().trim()); //n: 입력값
        a = new int[n+1]; //a: 입력 배열
        StringTokenizer str = new StringTokenizer(br.readLine().trim());
        for(int i = 1; i<=n; i++) {
            a[i] = Integer.parseInt(str.nextToken());
        }        
        left = new int[n+2]; //left[i]: i번째 index를 마지막 원소로 가지는 수열의 연속 합.
        right = new int[n+2]; //right[i]: i번째 index를 시작 원소로 가지는 수열의 연속 합.
        ans = a[1]; //ans:출력값
        for(int i = 1; i<=n; i++) {
            left[i] = a[i];
            left[i] = Math.max(left[i], left[i-1]+a[i]);
            if(left[i]>ans) ans = left[i]; //숫자를 삭제하지 않는 경우
        }
        for(int i = n; i>=1; i--) {
            right[i] = a[i];
            right[i] = Math.max(right[i], right[i+1]+a[i]);
        }
        for(int i = 1; i<=n; i++) { 
            //i번째 원소를 삭제한 경우, i-1번째를 마지막으로 하는 수열의 합과 i+1번째를 시작으로 하는 수열의 합을 더한 값.
            if(left[i-1]+right[i+1]>ans) ans = left[i-1]+right[i+1];
        }
        System.out.println(ans);
    }
}