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

문제링크 : https://www.acmicpc.net/problem/17216

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, arr[1001], dp[1001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;
    for(int i=0; i<N; i++) 
    {
        cin >> arr[i];
        dp[i]=arr[i]; //최솟값 (초기값)
    }

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<i; j++)
        {
            if(arr[i] < arr[j]) dp[i] = max(dp[i], dp[j]+arr[i]); //갱신
        }
    }

    int result = 0;
    for(int i=0; i<N; i++) result = max(result, dp[i]); //최대값 저장
    cout << result;
    return 0;
}

 

가장 큰 감소 부분 수열은 최솟값으로 자기 자신의 값을 가진다.

따라서 arr[i]의 값을 입력받는 동시에 dp[i]에 값을 저장해준다.

 

이후 2중 반복문을 통해 현재 i 기준 앞에 있는 값들을 체크한다.

현재 i보다 작다면 누적해야 더해주며 dp를 갱신하고 dp 값에 수열의 합이 담겼으니 최대값을 출력해주면 된다.