[Baekjoon] 1912번: 연속합

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

1912번: 연속합

문제 설명

DP를 활용한 기본 문제이다. DP가 늘 그렇듯이 반복되는 규칙을 찾아내고 점화식을 구하면 된다. 이 문제의 경우 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구해야 한다. 단, 수는 한 개 이상 선택해야 한다. 예제 입력 1을 가지고 보도록 하자.

앞에서부터 구해보자. 먼저 수를 단 한 개 이상 선택해야 한다고 했으므로 현재 최댓값은 10으로 하자.

그 다음 수인 -4와 더하면 10 + (-4) = 6이 된다. 이 값은 10보다 작으므로 max는 갱신되지 않는다.

그 다음 수인 3을 더해보자. 10 + (-4) + 3 = 9 이므로 max보다 작다. 따라서 갱신되지 않는다.

그 다음 수인 1을 더해보자. 10 + (-4) + 3 + 1 = 10 이므로 max보다 크지 않다. 따라서 갱신되지 않는다.

그 다음 수인 5를 더해보자. 10 + (-4) + 3 + 1 + 5 = 15 이므로 max보다 크다. 따라서 max를 15로 갱신한다.

여기서 돌아보면 연산 과정에서 반복이 발생되었다는 것을 알 수 있다. 다음 수 이전의 값들은 이미 계산된 값이므로 다시 계산할 필요가 없다. 이를 DP 배열로 만들어 저장하도록 하자.

 

현재 계산은 첫 번째 수부터 차례대로 더해가는 방식이다. 그러나 이런 식이면 10, -4, 3, ... 순으로 n만큼 반복을 계속 해야 한다. 이를 어떻게 해결할 방법이 없을까?

해결 방법은 DP 에 값을 저장할 때 이전까지 탐색했던 값과 현재 값을 비교해서 더 큰 수를 저장하는 것이다. -4를 더하는 경우를 생각해보자.

한 수는 기본적으로 선택되어야 하므로 10은 그대로 가져온다.

10에 -4를 더하면 6이 된다. 이 값과 현재 값인 -4와 비교하면 6이 더 크다. 이 값을 DP 배열에 저장하는 것이다.

그 다음엔 이전에 계산한 DP에 저장된 6에 3을 더한 9과 3을 비교한다. 9가 더 크므로 9를 DP에 저장한다.

이런 식으로 하다가 -35까지 더한 경우엔 다음과 같은 상황이 된다.

 여기서는 12가 -14 + 12인 -2보다 크므로 DP에 12를 저장한다.

그 다음 12 + 21 = 33이고 12보다 크므로 DP에 33을 저장한다. 그리고 max가 33보다 작으므로 max도 갱신한다.

이렇게 DP를 활용하여 O(N)으로 문제를 해결할 수 있다.

풀이 방법

DP는 Top-Down과 Bottom-Up 두 가지 방식으로 풀 수 있다. 위 설명을 이해했다면 어렵지 않게 코드로 구현할 수 있을 것이다.

Top-Down

private static int recur(int n) {
    if (dp[n] == null) {
        dp[n] = Math.max(recur(n - 1) + arr[n], arr[n]);
        max = Math.max(max, dp[n]);
    }

    return dp[n];
}

Bottom-Up

private static void bottomUp() {
    for (int i = 1; i < arr.length; i++) {
        dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
        max = Math.max(max, dp[i]);
    }
}

전체 코드

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

class Main {

    static int[] arr;
    static Integer[] dp;
    static int max;

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

        int n = Integer.parseInt(br.readLine());
        arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::valueOf).toArray();
        topDown(n - 1);
        // bottomUp();

        System.out.print(max);
    }

    private static void topDown(int n) {
        dp = new Integer[arr.length];
        dp[0] = arr[0];
        max = arr[0];

        recur(n);
    }

    private static int recur(int n) {
        if (dp[n] == null) {
            dp[n] = Math.max(recur(n - 1) + arr[n], arr[n]);
            max = Math.max(max, dp[n]);
        }

        return dp[n];
    }

    private static void bottomUp() {
        dp = new Integer[arr.length];
        dp[0] = arr[0];
        max = arr[0];

        for (int i = 1; i < arr.length; i++) {
            dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
            max = Math.max(max, dp[i]);
        }
    }
}