[Silver 2] 11053번 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

이 문제는 DP를 통해 해결할 수 있다.

 

문제의 점화식은 아래와 같다.

• 현재 검사하고하는 수 A가 배열에 저장된 수 B보다 클 경우
  • 또한, 현재 배열에 저장된 수 B의 count가 최대 값이 아닌 경우 최대 값을 변경
• 현재 검사한 자리 수의 counter를 최대 값 + 1로 변경

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int dp[1001];
int T;
int N, M, K, H;
int X, Y;
int answer = 0;

int main() {
    vector<int> v;
    cin >> T;

    for (int i = 0; i < T; i++) {
        cin >> K;
        v.push_back(K);
        int dp_max = 0;

        for (int j = 0; j < v.size(); j++) {
            if (v[i] > v[j]) {
                if (dp_max < dp[j])
                    dp_max = dp[j];
            }
        }
        dp[i] = dp_max + 1;
        answer = max(answer, dp[i]);
    }

    cout << answer << endl;

    return 0;
}