문제

이해

주어진 수열에서 합이 가장 큰 증가하는 부분 수열의 합을 출력해야 한다.

위의 예와 같이 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 에서의 합이 가장 큰 부분 수열은
{1, 2, 50, 60} 으로 합은 113이다.

증가하는 부분 수열의 기준은 문제에서의 조건으로는 없지만 수가 같은 경우는 포함하지 않는 것 같다.

접근

가장 먼저 떠오른 방법은 다이내믹 프로그래밍이다. 오름차순으로 이루어진 부분 수열은 경우에 따라서 다른 부분 수열에 포함될 수도 있기 때문이다.

dp[i]의 기준은 i로 시작하는 가장 큰 부분 수열의 합으로 정했다.

그렇다면 dp의 점화식을 생각해보자.

문제의 예제에서 dp[0] = 1 + 2 + 50 + 60 이다.

이를 다르게 보면 dp[0] = arr[0] + dp[2] 로도 표현할 수 있다.

또 다시 dp[2] = arr[2] + dp[3] 으로 표현 가능하고 dp[3] = arr[3] + dp[4] 로 표현 가능하다.

이를 통해 dp[i] = arr[i] + Max(dp[k]) (k는 i보다 큰 수 && arr[i] < arr[k]) 임을 알 수 있다.

다시 돌아와서 점화식을 dp[0]에 적용시켜 보자.

dp[0] = 1 + Max(dp[k])가 된다. dp[k]의 후보 중에는 dp[1], dp[2]가 있을 수 있게 된다.

물론 dp[3]와 dp[4]도 후보라고 할 수 있지만 이는 dp[2]에 모두 포함되므로 제외된다.

따라서, dp[1] = 100, dp[2] = 112 중 큰 값인 dp[2]가 선택되어 dp[0] = 113이 된다.

그렇다면 dp[i]의 결정 방식에 대해서 생각해보자.

다이나믹 프로그래밍의 결정 방식에는 bottom-up, top-down이 있는데 둘 중 아무거나 사용해도 상관없어 보인다.

top-down 방식에서는 dp[0]부터 시작해 재귀로 뻗어나가면 되고

bottom-up 방식에서는 dp[N-1]부터 시작해 dp[0]까지 구할 수 있다.

물론, 두 방식 모두 메모이제이션을 통해 시간복잡도를 줄일 수 있다.

코드

package java_baekjoon;

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

public class prob11055 {
    static int N;
    static int[] arr;
    static int[] dp;
    static int ans = 0;

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

        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        dp = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = N - 1; i >= 0; i--) {
            dp[i] = arr[i];
            int max_dp = 0;
            for (int j = i + 1; j < N; j++) {
                if (arr[i] < arr[j] && max_dp < dp[j]) {
                    max_dp = dp[j];
                }
            }
            dp[i] += max_dp;
            
            if(ans < dp[i]){
                ans = dp[i];
            }
        }

        System.out.println(ans);
    }
}

코드는 bottom-up 방식을 사용했다. N-1번째부터 시작하여 0까지 구한다.

반복과정 중에 최댓값을 갱신하여 끝에서 출력한다.

결과