[BOJ] 11722 - 가장 긴 감소하는 부분 수열 (C++)

문제

가장 긴 감소하는 부분 수열

코드

#include <iostream>

using namespace std;

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

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

    cin >> N;
    for (int i = 1; i <= N; i++) cin >> input[i];

    int m = 0;
    for (int i = 1; i <= N; i++){
        dp[i] = 1;
        for (int j = 1; j < i; j++){
            if (input[i] < input[j]) dp[i] = max(dp[i], dp[j]+1);
        }
        m = max(m, dp[i]);
    }

    cout << m;
    return 0;
}

접근

먼저 dp의 값을 1로 초기화 하고 이전 값들을 살펴보면서 값을 갱신시켜 주었다. 현재 값을 이전 감소 수열에 이을 수 있는지 확인하기 위해 두 값을 비교하고 dp 값을 dp[i]와 dp[j]+1 을 비교해서 갱신해준다. 중간에 위치한 값이 최대 값일 수 있기 때문에 매 순간 최대 값을 찾아서 유지한다.