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

---

와 진짜 이거 풀려고 한 이틀 정도 쓴 것 같다...
한 케이스를 해결하면 다른 케이스에서 문제가 나고, 또 이걸 해결하면 원래 케이스에서 오류가 나고...
그런데 결국 해결했다는 것!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class ContinuousSum2 {

    public static int stoi(String str) {
        return Integer.parseInt(str);
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = stoi(br.readLine());
        int[] arr = new int[N+1];
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i=1; i<=N; i++) {
          arr[i] = stoi(st.nextToken());
        }
        
        int[][] dp = new int[N+1][2];
        dp[1][0] = arr[1];
        dp[1][1] = arr[1];
        
        for (int i=2; i<=N; i++) {
          dp[i][0] = Math.max(arr[i], dp[i-1][0]+arr[i]);
          dp[i][1] = Math.max(dp[i-1][1] + arr[i], dp[i-1][0]);
        }
        
        int max = Integer.MIN_VALUE;
        for (int i=1; i<=N; i++) {
          if (dp[i][0] > max) {
            max = dp[i][0];
          }
          if (dp[i][1] > max) {
            max = dp[i][1];
          }
        }
        System.out.println(max);
    }
}

dp[i][0]은 수열에 자신이 포함될 경우를 뜻한다. 따라서 제외되는 요소가 없다. 자기 자신의 값(arr[i])과 이전 수열에서 나를 더한 값(dp[i-1][0]+arr[i]) 중 더 큰 값을 저장한다. 즉 일반적인 연속합을 구한 배열!

 

dp[i][1]은 수열에 어느 한 값을 포함하지 않은 경우를 뜻한다. 이것 역시 두 가지 케이스로 나눠서 구할 수 있는데,

1. 이전에 수 하나를 제외한 수열에 나를 포함시키는 것(dp[i-1][1] + arr[i])
2. 이전에는 제외된 수가 없었고, 나를 제외시키는 것(dp[i-1][0])
이 두 가지 케이스 중 더 큰 값을 저장하면 된다.

 

로그인