백준 13998번 - 연속합2 / Java

문제

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

13398번: 연속합 2

연속합에서 하나를 제거할 수 있다는 조건이 붙은 문제.

처음에는 하나를 제거할때 마다 모든 경우의 수를 계산해보려고 했다.

그러나 아래의 문제점이 발견해서 다른 해결법으로 풀었다.

 

1. 시간 복잡도를 O(N)에 해결할경우 메모리를 많이써야해서 메모리 초과

2. 시간복잡도를 O(N^2)에 해결할 경우 시간 초과.

 

그래서 k번째 수를 제거하는 연속 합일 경우 k-1번째까지의 연속합과 k+1부터의 연속합을 더해서 값을 구하는 방식으로 풀었다.

 

 

알고리즘

1. 1번째부터 n번째까지의 연속합을 dp1에 저장한다

2. n번째부터 1번째까지의 연속합을 dp2에 저장한다

3. 1부터 n까지 k번째수를 빼고 연속합을 구한다. dp1[k-1]+dp2[k+1]

4. 구한 연속합중에서 최댓값을 출력한다

 

소스코드

/*
 * BOJ13398
 * 2020.01.19
 * Hyeonseong
 */
import java.util.*;
public class BOJ13398
{
    public static void main(String[] args) 
    {
        Solution s = new Solution();
    }
}
class Solution{
    public Solution() {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
 
        int[] arr = new int[n+1];
        int[] dp1 = new int[n+1];
        int[] dp2 = new int[n+1];
        for(int i=1;i<n+1;i++) {
            arr[i] = scan.nextInt();
        }
        dp1[1] = arr[1];
        for(int i=2;i<n+1;i++) {
            dp1[i] = Math.max(dp1[i-1]+arr[i],arr[i]);
        }
        
        dp2[n] = arr[n];
        for(int i=n-1;i>=0;i--) {
            dp2[i] = Math.max(dp2[i+1]+arr[i],arr[i]);
        }
        
        int answer = Integer.MIN_VALUE;
        for(int i=1;i<n+1;i++) {
            answer = Math.max(answer,dp1[i]);
        }
        
        for(int i=1;i<n;i++) {
            answer = Math.max(answer, dp1[i-1]+dp2[i+1]);
        }
        System.out.println(answer);
    }
}