[java 백준] 골드 5/13398번 연속합2

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

13398번: 연속합 2

import java.io.*;
import java.util.*;
 
import static java.lang.Math.max;
 
public class Main {
 
    public static int n;
    public static int []arr;
    public static int [][]dp;
    public static int max;
    public static void main(String[]args) throws IOException {
        Scanner sc=new Scanner(System.in);
        //자기자신을 포함했을 때와 하지 않았을때로 구분해서 생각해야
        //dp[n][0] n번째가 연속합의 마지막이면서  수 하나를 제거하지 않았을 때
        //dp[n][1] n번째 수가 연속합의 마지막이면서 특정 수 하나를 제거했을 때
 
        n=sc.nextInt();
        arr=new int[n];
        dp=new int[n][2];
 
 
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        dp[0][0]=arr[0];
        dp[0][1]=0;
        max=arr[0]; // 원소가 하나있을 때 반례 해결 가능 예를 들면
        //1
        //-3
        //입력받았을 때
 
        for(int i=1;i<n;i++){
            dp[i][0]=Math.max(dp[i-1][0]+arr[i],arr[i]);
            // 한번도 제거하지 않고 i번째 까지 계속 쌓아올리는 경우 or i번째에서 연속합 시작
            dp[i][1]=Math.max(dp[i-1][0],dp[i-1][1]+arr[i]);
            // 특정수를 처음 제거하는 경우 or 이전에 한번 제거 됐기 때문에 이번엔 더해주기
 
            max=Math.max(max,Math.max(dp[i][0],dp[i][1]));
 
        }
        System.out.println(max);
 
 
 
 
 
    }
 
 
 
 
 
 
 
}

 

처음엔 카데인 알고리즘 이런것들을 찾아봤는데 알고보니 원소를 제거하냐 마느냐로 구분하는게 더 중요했다. 2차원 배열을 사용하여 dp[i][0]은 i번째까지 순서를 돌았을 때 특정수가 제거된적이 한번도 없는경우

dp[i][1]은 i번째까지 순서를 돌았을 때 특정수가 제거된적이 있는 경우로 나눠볼 수 있다.

 

1) dp[i][0]

 

Math.max(dp[i-1][0]+arr[i],arr[i])

 

--> 지금까지 한번도 제거하지 않고 쭉 쌓아온경우 or i번째부터 연속합을 새로 시작하는 경우 

 

2)dp[i][1] 

 

Math.max(dp[i-1][0],dp[i-1][1]+arr[i])

 

--> i번째를 처음으로 포함하지 않은 경우, 즉 이번에 처음으로 제거한 경우 or 이전에 제거했기 때문에 이번에는 arr[i]를 더해주는 경우 

특정수를 한번만 제거할 수 있다 그래서 그러면 어떻게 한번만 제거한걸 count해주지 싶었는데 어차피 최대값이기때문에 한번만 제거한게 당연히 큰 값일 수 밖에 없어서 굳이 생각할 필요가 없었다. 

 

마지막으로 중요한것은 max=0으로 두는게 아니라 max=arr[0]으로 두는거다.

예를 들어

1

-3

같이 원소가 하나만 입력됐을 때는 max자체가 arr[0]이기 때문이다!

 

도움을 받은 글 

https://steady-coding.tistory.com/181

[BOJ] 백준 13398번 : 연속합 2 (JAVA)