[C++] 백준 11053 가장 긴 증가하는 부분 순열

11053 가장 긴 증가하는 부분 순열

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

C++

#include <iostream>
#include <vector>

using namespace std;

vector<int> per;

int main() {
    int n, input;
    cin >> n;
    vector<int> memo(n);        // 거기까지의 최대 길이

    for (int i = 0; i < n; i++) {
        cin >> input;
        per.push_back(input);   // 들어가 있는 실제 수
    }

    memo[0] = 1;
    for (int i = 1; i < n; i++) {
        int max = -1;
        bool isMax;
        isMax = false;
        for (int j = 0; j < i; j++) {
            if (per[j] < per[i] && memo[j] > max) {
                max = memo[j];
                isMax = true;
            }
        }
        if (isMax == true) memo[i] = max + 1;
        else memo[i] = 1;
    }

    int MAX = 1;
    for (int i = 0; i < n; i++){
        if (MAX < memo[i]) MAX = memo[i];
    }

    cout << MAX << endl;

    return 0;
}

 

per 배열에는 들어가 있는 실제 수를 저장하고,

memo[i]에는 i번째 수까지 보았을 때 구할 수 있는 가장 긴 부분 수열의 길이를 저장한다.

 

첫번째 이중 for문을 통해 memo 배열을 모두 채워주고

마지막 for문을 통해 memo 안의 값 중 최대값을 찾아내서 출력한다.