[BOJ/Java] 11055. 가장 큰 증가 부분 수열

[BOJ/Java] 11055. 가장 큰 증가 부분 수열

11055번: 가장 큰 증가하는 부분 수열

---

문제 해석

주어진 수열에서 증가 부분 수열을 찾아 그 합이 최대가 되는 값을 구하는 문제이다. 이는 '가장 긴 증가하는 부분 수열' 문제의 변형으로, 길이가 아닌 수열의 합을 최대화하는 것이 목표이다.

풀이 과정

1. 입력 받기: 수열의 크기 N과 수열 A를 입력 받는다.
2. 동적 프로그래밍(DP) 배열 초기화: DP 배열을 사용하여 각 위치에서 가능한 최대 합을 저장한다.
3. DP 배열 채우기: 수열 A를 순차적으로 탐색하면서, 각 요소보다 작은 요소들의 DP 값에 현재 요소를 더한 값과 현재의 DP 값을 비교하여 최대값을 갱신한다.
4. 최대값 추출: DP 배열에서 가장 큰 값을 찾아 반환한다.

코드

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

public class Main {
    private static int N; // 수열의 크기
    private static int[] A, dp; // 수열 A와 동적 프로그래밍을 위한 배열 dp

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine()); // 수열의 크기 입력

        A = new int[N]; // 수열 A 초기화
        StringTokenizer st = new StringTokenizer(br.readLine()); // 수열 A의 원소들 입력
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        sb.append(sol()); // 가장 큰 증가 부분 수열의 합을 계산하고 결과를 StringBuilder에 추가
        bw.write(sb.toString()); // 결과 출력
        bw.flush();
        bw.close();
    }

    private static int sol() {
        dp = new int[N]; // dp 배열 초기화
        dp[0] = A[0]; // 첫 번째 요소는 자기 자신으로 시작
        for (int i = 1; i < N; i++) {
            dp[i] = A[i]; // 초기값 설정
            for (int j = 0; j < i; j++) {
                if (A[i] > A[j]) dp[i] = Math.max(A[i] + dp[j], dp[i]); // 이전 요소들과 비교하여 최대 합 갱신
            }
        }

        int ans = Integer.MIN_VALUE; // 최대값을 찾기 위한 초기값 설정
        for (int d : dp) ans = Math.max(ans, d); // dp 배열에서 최대값 찾기
        return ans; // 최대값 반환
    }
}

시간 복잡도 분석

이 문제의 시간 복잡도는 𝑂(𝑁^2)이다. 수열의 각 요소에 대하여 이전의 모든 요소들을 검사하기 때문에, 최악의 경우 𝑁×(𝑁−1)/2 번의 비교가 이루어진다.

느낀점

가장 큰 증가 부분 수열 문제는 동적 프로그래밍을 통해 해결할 수 있는 대표적인 예제 중 하나이다. 문제를 풀면서 동적 프로그래밍의 기본 원리를 활용하여 문제를 체계적으로 분해하고 해결하는 방법을 더욱 깊이 이해할 수 있었다. 이러한 접근 방식은 다른 복잡한 문제에도 응용할 수 있는 기초를 제공한다.