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

문제

가장 긴 증가하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

---

풀이

동적 계획법(Dynamic Programming)을 사용하는 문제이다.

dp[i]의 값은 num[i]을 가장 큰 수로 가지는 가장 긴 증가하는 부분 수열의 길이를 나타낸다.

따라서, num 배열에서 0 ~ i-1의 수를 비교하며 해당 숫자가 num[i] 보다 작은 경우에서 dp 배열의 값이 가장 클 때의 길이 +1
를 하면 dp[i]를 구할 수 있다.

---

코드

#include <iostream>
#include <vector>

using namespace std;

void solve();
vector<int> input(int *n);

int main() {
    solve();

    return 0;
}

void solve() {
    int n, ans = 1;
    vector<int> num;

    num = input(&n);

    vector<int> dp(n, 1);

    dp[0] = 1;

    for (int i = 1; i < n; i++) {
        int temp = 0;

        for (int j = 0; j < i; j++) {
            if (num[i] > num[j]) { // 현재 수보다 비교하는 수가 작은 경우에만 증가 수열임
                temp = temp > dp[j] ? temp : dp[j]; // 가장 긴 길이를 저장
            }
        }

        dp[i] = temp + 1; // 숫자 하나가 더 늘어났기 때문에 +1

        if (dp[i] > ans) { // 가장 긴 길이를 저장
            ans = dp[i];
        }
    }

    cout << ans;
}

vector<int> input(int *n) {
    cin >> *n;

    vector<int> num;
    int temp;

    for (int i = 0; i < *n; i++) {
        cin >> temp;
        num.push_back(temp);
    }

    return num;
}