알고리즘 풀이 - 백준 13398(연속합2, DP)

 

관련글

 

Dynamic Programming 관련 포스팅은 여기를 참조
관련 문제인 1912번(연속합) 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

 

이 문제는 배열의 연속합을 구하되 특정 값을 제거하거나 제거하지 않을 수 있는 옵션이 붙은 문제이다.

 

 

2. 풀이

 

우선 문제를 이해하자. 배열 내에서 단순히 값을 몇 개 뽑아서 더하는 것이 아니라 연속합 중 최대의 경우를 구해야 한다.
연속합은 1개만 있어도 연속합이 될 수 있다.

아래와 같은 배열이 있을 때를 예시로 조금만 알아보자. arr[i]는 원 배열이고, sum[i]는 연속합이 최대가 되는 경우의 배열이다.

인덱스 i	0	1	2	3
arr[i]	10	-12	30	-8
sum[i]	10	-2	30	22

 

sum[i]을 보며 왜 저렇게 되었는지 알아보자.

index=0일 때, 현재 위치 기준 최대 연속합은 자기 자신 뿐이므로 sum[0] = 10
index=1일 때, 현재 위치 기준 최대 연속합은 자기 자신 보다는 이전과의 합이므로 10+(-12)가 되어 sum[1] = -2
index=2일 때, 현재 위치 기준 최대 연속합은 자기 자신이 이전과의 합보다 크므로 sum[2] = 30
index=3일 때, 현재 위치 기준 최대 연속합은 자기 자신 보다는 이전과의 합이므로 30+(-8)이 되어 sum[3] = 22

 

즉, 현재 위치 기준 최대 연속합은 이전 연속합과 더하거나 더하지 않거나 2가지 중 한 가지가 된다.

 

위를 기반으로 점화식을 만들 수 있으며, 각 부분에서 이전의 결과가 반복적으로 사용되고 해당 최적 결과값이 그대로 사용되니 DP의 두 가지 조건인 Overlapping Subproblems와 Optimal Substructure를 만족하여 DP로 풀 수 있다.

 

 

그런데, 이 문제는 한 가지의 옵션이 더 있다. 중간에 값을 하나 제외해도 된다는 것!

기본적으로 생각할 수 있는 아이디어는, 각 위치의 숫자를 탐색하면서 이전의 숫자들 중 일부를 제외하는 경우를 모두 체크하는 경우가 있을 수 있다.

하지만 그 경우, 2중 반복문을 활용하기에 $O(N^2)$의 시간복잡도가 도출되어 최대 10만개의 숫자라면 시간초과가 발생한다.

 

사실 이 문제는 간단한 아이디어를 통해 해결할 수 있다. 

현재 값을 기준으로 좌측의 연속합, 우측의 연속합을 더하면 현재 값을 제외한 결과값 중 최대의 값을 구할 수 있게 된다.

 

 

그렇다면, DP로 풀 수 있으니 저장할 State의 정의를 한 번 세워보자. 여기서 State는 배열의 길이에 따른 위치 뿐이다. 아래와 같을 것이다. 따라서 1차원으로 저장할 수 있다.

좌측에서 부터의 연속합은 left, 우측을 right 배열이라고 바꿔서 쓰자.(DP 문제임을 강조하기 위해..)
정의 ▼
left[N] = 위치 N에서의 좌측에서부터의 연속합의 최대값
right[N] = 위치 N에서의 우측에서부터의 연속합의 최대값

 

기저 상태와 점화식을 알아보자.

기저 상태는 좌측은 index가 0일 때, 우측은 N-1일 때이다. 해당 경우에는 원 배열의 값을 그대로 적용한다.
기저 상태 : left[0] = arr[0],  right[N-1]=arr[N-1]

점화식은 이전의 연속합과 합하거나 하지 않거나 이므로 그 중 더 큰 값으로 구한다.
점화식 :
left[N] = Math.max(left[N-1] + arr[N], arr[N])
right[N] = Math.max(right[N+1]+arr[N], arr[N])

 

그러면 결과는 아래와 같이 구할 수 있다. 현재 위치의 값을 빼고 계산하거나 값을 포함 시켜 계산하는 경우를 모두 연산해야 한다.
결과 ▼
result[N] = MAX(left[N-1] + right[N+1], left[N])

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

1) Bottom-up 방식

import java.io.*;

public class Main {
    static int arr[];
    static int left[];
    static int right[];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        arr = new int[n];
	    left = new int[n];
        right = new int[n];

        String line[] = br.readLine().split(" ");
        
        int result = Integer.MIN_VALUE;
        
        // 우선 좌측에서 시작하는 연속합의 최대 경우를 구함
        for(int i=0; i < n; i++){
            arr[i] = Integer.parseInt(line[i]);
            if(i == 0) {
                left[i] = arr[i];
            } else {
                left[i] = Math.max(left[i-1] + arr[i], arr[i]);
            }
            
            // 특정 값을 빼지 않고도 최대값이 되는 경우가 있으니 이 또한 고려
            result = Math.max(result, left[i]);
        }
        
        // 우측에서 시작하는 연속합의 최대 경우를 구함
        for(int i=n-1; i >= 0; i--){
            if(i == n-1){
                right[i] = arr[i]; continue;
            }
            right[i] = Math.max(right[i+1] + arr[i], arr[i]);
        }
        
        // 특정 index를 빼고 좌 우측의 합으로만 수행하기
        for(int i=1; i < n-1; i++){
            result = Math.max(result, left[i-1] + right[i+1]);
        }
        
        bw.write(String.valueOf(result));
        br.close();
        bw.flush();
    }
}

 

2) Top-Down 방식

import java.io.*;

public class Main{
    static int[] arr;
    static int[] left;
    static int[] right;
    static int n; // 여기에 써야 우측 부터 시작 시 n에 바로 접근(혹은 parameter로 전달해도됨)
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        n = Integer.parseInt(br.readLine());
        String s[] = br.readLine().split(" ");
        
        arr = new int[n];
        left = new int[n];
        right = new int[n];
        
        for(int i=0; i < n; i++){
            arr[i] = Integer.parseInt(s[i]);
            left[i] = Integer.MIN_VALUE; // Top-Down에서는 반환 조건을 위해 초기에 최소값으로 지정
            right[i] = Integer.MIN_VALUE;
            // 문제에서 -1000 ~ 1000까지만 나오고 100,000개 이므로 최소 -1억이다.
            // 이를 기반으로 아래에서 조건식 지정
        }
        
        topDown_left(n-1);
        
        // 특정 값을 빼지 않고도 최대값이 경우가 있을 수 있다!
        int result = Integer.MIN_VALUE;
        for(int i=0; i < n; i++){
            result = Math.max(result, left[i]);
        }
        
        topDown_right(0);
        
        // 특정 값을 빼고 최대값이 나오는 경우를 위해 추가
        for(int i=1; i < n-1; i++){
            result = Math.max(result, left[i-1] + right[i+1]);
        }
        
        bw.write(String.valueOf(result));
        br.close();
        bw.flush();
    }
    
    // Top-Down 방식 좌측에서 시작
    public static int topDown_left(int k){
        // 여기서 반환 조건식을 지정함
        // 값이 최소값이 아니거나 k=0이면 반환
        if(k == 0) return left[k] = arr[k];
        if(left[k] > Integer.MIN_VALUE) return left[k]; 
        
        // 재귀를 통해서 값을 구해온다.
        return left[k] = Math.max(topDown_left(k-1) + arr[k], arr[k]);
    }
    
    // Top-Down 방식 우측에서 시작
    public static int topDown_right(int k){
        // 여기서 반환 조건식을 지정함
        // 값이 최소값이 아니거나 k=0이면 반환
        if(k == n-1) return right[k] = arr[k];
        if(right[k] > Integer.MIN_VALUE) return right[k];
        
        // 재귀를 통해서 값을 구해온다.
        return right[k] = Math.max(topDown_right(k+1) + arr[k], arr[k]);
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.