[백준/DP/C++] 11053번 가장 긴 증가하는 부분 수열

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

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

전에 풀어봤던 문제라서 쉽게 해결됐다
배열 a에 수열을 넣고 dp배열에는 i번째 값을 포함하는 가장 긴 수열의 수를 넣는다

dp배열은 1로 초기화하고
a값을 차례대로 비교하면서 자신의 값보다 작은 값의 dp값에 1을 더해준다

#include <bits/stdc++.h>

using namespace std;
int n;
int dp[1001] = {0}, a[1001] ={0};

int main(void) {
    cin >> n;

    for(int i=1; i<=n; i++){
        cin >> a[i];
        dp[i] = 1;
    }

    dp[1] = 1;
    for(int i=2; i<=n; i++){
        for(int j=1; j<i; j++){
            if(a[i]>a[j])
                dp[i] = max(dp[i], dp[j]+1);
        }
    }

    int result = 0;
    for(int i=1; i<=n; i++){
        result = max(result, dp[i]);
    }
    cout << result << endl;

    return 0;
}

반응형