[백준 11055] 가장 큰 증가 부분 수열 (C++)

문제 출처 : https://www.acmicpc.net/problem/11055

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

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, result = 0;
    cin >> n;
    int arr[1001] = {0}, dp[1001] = {0};
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    dp[0] = result = arr[0];
    for (int i = 1; i < n; i++) {
        for (int j = i - 1; j >= 0; j--) {
            if (arr[i] > arr[j] && dp[i] < dp[j] + arr[i]) {
                dp[i] = dp[j] + arr[i];
                result = max(result, dp[i]);
            }
        }
        if (dp[i] == 0) dp[i] = arr[i];
    }
    cout << result;
    return 0;
}

알고리즘

- 다이나믹 프로그래밍

 

수열 A의 크기를 n에 담고, arr[] 배열에 수열 A를 담았다.

dp[i]에는 arr[i]를 포함한 가장 큰 증가 부분 수열의 합이 들어간다.

dp[0]은 arr[0]을 포함한 가장 큰 증가 부분 수열의 합이므로 arr[0]을 그대로 넣어준다.

result에는 답을 넣어줄 것인데 현재 가장 큰 증가 부분 수열의 합은 dp[0] (arr[0])이므로 그대로 넣어준다.

 

이후 반복문을 돌며 나머지 배열을 확인한다.

자신보다 값이 작은 배열값을 찾는다.

현재 저장되어 있는 자신을 포함한 가장 큰 증가 부분 수열의 합 (dp[i])보다 해당 값을 포함한 가장 큰 증가 부분 수열의 합 (dp[j])에 자신 (arr[i])을 포함한 값이 더 크다면 이를 업데이트 해준다.

result도 더 큰 값으로 업데이트 해준다.

 

arr[0]까지 다 확인했음에도 dp[i]가 0값을 가진다면 자신보다 작은 값을 가지는 배열값이 없다는 의미이므로 자신을 포함한 가장 큰 증가 부분 수열의 합은 자기 자신이 된다. dp[i]에는 arr[i]값을 넣어준다.

 

모든 배열값을 확인했다면 result값을 출력한다.