[백준 17216번] 가장 큰 감소 부분 수열

문제 링크

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

 

문제 요약

주어진 수열 \(A\)에서 합이 가장 큰 감소하는 부분 수열을 찾는 문제이다.

 

문제 풀이

감소하는/증가하는 부분 수열을 찾는 문제는 전형적인 동적 계획법(Dynamic Programming) 문제들 중 하나이다. 이 문제 역시 점화식을 세워 동적 계획법으로 문제를 해결할 수 있다.

 

점화식을 세우기 전에 DP 배열부터 정의를 해보자. \(dp[i]\)는 수열 \(A\)에서 \(A[i]\)로 끝나는 감소 부분 수열의 합 중에서 가장 큰 값을 저장하는 배열이다.

 

그다음으로 DP 배열을 초기화한다. 각 원소는 자기 자신만을 포함하는 감소 부분 수열이 될 수 있으므로, \(dp[i]\)의 초기값을 \(A[i]\)로 설정한다.

 

이제 제일 중요한 점화식을 세우는 과정이다. 감소하는 부분 수열을 만들어야 하므로, \(i\)번째 원소를 기준으로 이전 위치의 원소들 중 \(i\)보다 큰 \(A[j]\)를 찾는다. 만약 \(A[j]\)가 \(A[i]\)보다 크다면, \(A[j]\)로 끝나는 감소 부분 수열의 최대 합에 \(A[i]\)를 더해 새로운 최대 합을 업데이트할 수 있다. 이를 바탕으로 점화식을 세우면 다음과 같다.

$$dp[i] = \max(dp[i], dp[j] + A[i]) \quad \text{(단, } j < i \text{ 그리고 } A[j] > A[i])$$

이중 반복문을 사용해 모든 \(i\)에 대해 자신보다 앞선 \(j\)들을 확인하기 때문에 시간 복잡도는 \(\mathcal{O}(n^2)\)이다. 하지만 \(n\)이 크지 않기 때문에 시간제한 내에 충분히 통과할 수 있다.

 

소스 코드

#include <stdio.h>
#include <algorithm>

using namespace std;

int n, A[1010], dp[1010];

int main() {
    scanf("%d", &n);
    
    for (int i = 0 ; i < n ; ++i) {
        scanf("%d", &A[i]);
    }

    for (int i = 0 ; i < n ; ++i) {
        dp[i] = A[i];

        for (int j = 0 ; j < i ; ++j) {
            if (A[j] > A[i]) {
                dp[i] = max(dp[i], dp[j] + A[i]);
            }
        }
    }
    
    int ans = 0;
    
    for (int i = 0 ; i < n ; ++i) {
        ans = max(ans, dp[i]);
    }
    
    printf("%d\n", ans);
}