백준 11053번, 가장 긴 증가하는 부분 수열

백준 11053번 c++ 문제풀이

문제:

백준 11053

풀이:

1. 다이나믹 프로그래밍으로 접근
2. 벡터에 수열 입력받기.
3. 현재 위치에서 이전 수들을 비교 후, 현재 위치의 값보다 작은 값을 발견하면 그 위치의 가장 긴 부분 수열 길이에 +1을 한 값들을 비교하여 가장 큰 값이
   현재 위치의 가장 긴 부분 수열 길이이다.

코드:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;   

int dp[1001] = {0, };

void dp_sol(vector<int> anum){
    int result = 0;
    for(int i=1;i<anum.size()+1;i++){
        dp[i] = 1;//1로 시작해서 아래 max 부분에서 최댓값을 찾으면 된다.
        for(int j=i-1;j>=1;j--){
            if(anum[i-1] > anum[j-1]){//현재 위치의 수보다 작은 수들을 찾아 그 곳까지의 부분 수열의 길이 중 가장 큰 값에 +1 을 해주면된다.
                dp[i] = max(dp[i], dp[j] +1);//최대 수열값 최신화 해주기
            }
        }
        if(dp[i] > result){
            result = dp[i];
        }
    }
    cout << result;
}

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

    int a;
    vector<int> anum;

    cin >> a;

    for(int i=0;i<a;i++){
        int input;

        cin >> input;

        anum.push_back(input);
    }

    dp_sol(anum);

    return 0;
}

감사합니다.