[백준] 17216번 : 가장 큰 감소 부분 수열 (C++)

17216번 : 가장 큰 감소 부분 수열

---

문제)

수열 A가 주어졌을 때, 그 수열의 감소 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5} 인 경우에 합이 가장 큰 감소 부분 수열은 A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5} 이고, 합은 186이다.

 

 

 

입력 :

첫째 줄에 수열 A의 크기 N(1 ≤ N ≤ 1000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다.(1 ≤ Ai ≤ 1,000)

 

 

출력 :

첫째 줄에 수열 A의 합이 가장 큰 감소 부분 수열의 합을 출력한다.

 

 

 

 

 

 

풀이)

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n;
vector<int> vec;
int dp[1001][1001];
 
int recur(int cur, int prev)
{
    int ret = 0;
 
    // 이미 구한 값이라면
    if (dp[cur][prev] != -1) return dp[cur][prev];
 
    // 이전에 가지고 온 값보다 작은 값이 있다면
    // 다음 recur로 넘어가 보고, 그 중 최대값을 
    // ret에 저장한다.
    for (int i = cur; i < n; i++)
    {
        if (prev > vec[i])
        {
            ret = max(ret, recur(i, vec[i]) + vec[i]);
        }
    }
 
    dp[cur][prev] = ret;
 
    return ret;
}
 
int main()
{
    cin >> n;
    vec.resize(n);
    for (int& e : vec) cin >> e;
    
    fill(&dp[0][0], &dp[1000][1000], -1);
    
    // Ai는 최대 1000이므로 1001을 이전 값으로 넣어준다.
    cout << recur(0, 1001);
 
    return 0;
}
 

---

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

17216번: 가장 큰 감소 부분 수열