[Java] 1912번: 연속합 Silver 2

문제 링크

이 문제를 처음 봤을 때, 필요한 변수는 두 개라고 생각했다.

1. 가장 큰 값을 저장할 변수
2. 누적 합을 저장할 변수

그리고 음수를 만날 때까지 수열을 계속 누적 합하고, 그때까지의 누적 합의 최댓값을 갱신하고, 양수를 만나면 다시 그 값을 시작으로 누적 합을 계산하면 된다고 생각했다.

그런데 정말 단순하게만 생각해 봐도 틀렸다는 것을 금방 깨달을 수 있었다.
입력이 10 20 -5 10 이렇게 주어진다면, 오히려 전체를 더했을 때가 10 20만 더했을 때보다 크기 때문이다..

그렇다면 누적 합을 어디서 끊어야 할지를 고민해 봤다.

입력이 10 20 -5만 주어진다면 10 20까지만 누적 합을 하다가 -5를 더했을 때의 누적 합이 더 작은 것을 알기 때문에 답을 도출할 수 있을 것이다.

여기서 입력이 하나 더 늘어서 아까처럼 10 20 -5 10이 주어진다면, 음수인 -5를 만났다고 해서 기존의 값을 지워버려서는 안 된다. 여기에다가 10을 더하는 경우까지 마저 고려해 보고 둘 중에 더 큰 값을 채택해야 한다.

그렇기에 누적 합을 갱신하는 기준은 새로운 값을 만나고, 그 값이 기존의 누적 합에 그 값을 더한 경우보다 더 큰 경우에만 갱신을 해야하는 것이다.

그래서 이렇게 정리할 수 있다.
새로운 값을 만났을 때,

1. 그 값(arr[i])만을 사용한 것과 그 값(sum + arr[i])을 누적 합한 것 중에서 더 큰 값으로 갱신한다.

   • 입력이 10 20 -35 10 30 였다면, 10 20 -35까지 누적 합(-5)을 한 상태에서 뒤에 10을 마저 누적 합 할지, 10을 새로 갱신해서 사용할지 고민하면, 당연히 10을 새로 갱신해서 사용하는 것이 낫다.
     즉, 이 과정이 현재 값을 포함한 누적합을 계속 유지할지 아니면, 새로 시작할지를 결정 짓는 것이다.

2. 갱신한 값으로 최댓값을 갱신한다.
   최댓값을 출력한다.

그래서 코드를 이렇게 작성할 수 있다.

정답

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N 입력 받기
        int N = Integer.parseInt(br.readLine());

        // 배열 입력 받기
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 탐색
        int sum = arr[0], maxSum = arr[0];
        for (int i = 1; i < N; i++) {
            sum = Math.max(arr[i], sum + arr[i]);
            maxSum = Math.max(sum, maxSum);
        }

        // 출력
        System.out.println(maxSum);
    }
}