백준 13398번 연속합2 [JAVA]

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 수를 제거하지 않았을 때의 정답은 12+21인 33이 정답이 된다.

만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.

입력

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

출력

첫째 줄에 답을 출력한다.

 

 

 

 

 

이 문제는 연속합 문제에서 좀 더 심화된 문제이다 

 

연속된 수의 합중 최댓값을 구하는 문제이고

수를 1개 삭제할수 있다는 추가조건이 붙었다

 

나는 이 문제를 딱보고

 

1. 아무 숫자도 삭제 안했을때 연속합의 최댓값 

 

2. 숫자 1개씩 지웠을때 각각의 상태에서의 연속합 최댓값

 

1과 2를 비교해서 큰것이 답일거라고 생각했다

 

그래서 기분좋게 코드를 작성하고 

 

틀린 코드

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] list=new int[n+1];
        int[] dp=new int[n+1];
        int[] delete=new int[n+1];
        int[] dp2=new int[n+1];

        for(int i=1;i<n+1;i++){
            list[i]=sc.nextInt();
        }

        dp[1]=list[1];
        for(int i=2;i<n+1;i++){
            if(dp[i-1]+list[i]>list[i])
                dp[i]=dp[i-1]+list[i];
            else
                dp[i]=list[i];
        }
        int max=0;

        for(int i=1;i<n+1;i++){
            int number=list[i];
            list[i]=0;
            for(int j=1;j<n+1;j++){
                if(delete[j-1]+list[j]>list[j])
                    delete[j]=delete[j-1]+list[j];
                else
                    delete[j]=list[j];
            }
            for(int k=1;k<n+1;k++){
                if(max<delete[k])
                    max=delete[k];
            }
            dp2[i]=max;
            list[i]=number; //원상복귀
        }

        int max1=dp[1];
        int max2=dp2[1];

        for(int i=2;i<n+1;i++){
            if(max1<dp[i])
                max1=dp[i];
        }


        for(int i=2;i<n+1;i++){
            if(max2<dp2[i])
                max2=dp2[i];
        }

        if(max1>max2)
            System.out.print(max1);
        else
            System.out.print(max2);

    }
}

 

테스트 케이스에 대한 답도 맞길래 기분좋게 제출을 했더니 시간초과~~~~...

그래.. 뭔가 코드를 짜면서 시간복잡도가 개망했다는것은 느끼고 있었다 

결국 답을 봤다..

결론은 어떤 수 list[i]를 지웠을때 또 그때마다 연속합의 최댓값을 구하는것은 비효율적이라는것이다. 

 

 

대신 다른 방법이 있다

우리는 지난 연속합 문제에서 

dp[k]를 처음부터 k번째 수까지 나올수 있는 연속합중에서 최댓값이라고 정의하고 문제를 해결하였다

이 문제는 삭제까지 해야된다 삭제를 할때 연속합은 어떻게 구해야될까

1. 삭제안했을때 나오는 연속합의 최댓값

2. list[1]~list[k]를 1개씩 삭제함으로써  k-1번째수와 k+1번째수가 연결되므로 따져야할 경우가 추가 된다 

바로

1번째수부터 k-1번쨰수까지 나오는 연속합의 최댓값 + k+1번째수부터 끝까지 나오는 연속합의 최댓값 이다

 

이를 위해 우리는 k번째 수로 끝나는 연속합의 최댓값 말고

k번째 수로 시작하는 연속합의 최댓값도 구해야한다 -> dp2배열이 필요한이유 (진짜 이걸 어떻게 생각해내냐..?)

 

 

1과 2를 비교해서 나오는 최댓값이 삭제까지 따져줬을때 나오는 연속합의 최댓값이다

 

정답 코드

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] list=new int[n+1];
        int[] dp=new int[n+1];
        int[] dp2=new int[n+1];

        for(int i=1;i<n+1;i++){
            list[i]=sc.nextInt();
        }

        dp[1]=list[1];
        for(int i=2;i<n+1;i++){
            if(dp[i-1]+list[i]>list[i])
                dp[i]=dp[i-1]+list[i];
            else
                dp[i]=list[i];
        }

        dp2[n]=list[n];
        for(int i=n-1;i>=1;i--){
            if(dp2[i+1]+list[i]>list[i])
                dp2[i]=dp2[i+1]+list[i];
            else
                dp2[i]=list[i];
        }

        for(int i=1;i<n;i++){
            dp2[i]=dp[i-1]+dp2[i+1];
        }

        int max1=dp[1];
        for(int i=1;i<n+1;i++){
            if(max1<dp[i])
                max1=dp[i];
        }
        int max2=dp2[1];
        for(int i=1;i<n+1;i++){
            if(max2<dp2[i])
                max2=dp2[i];
        }

        System.out.print(Math.max(max1,max2));
    }
}