가장 긴 증가하는 부분 수열 4 , 백준 14002

문제

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

이것도 LIS 시리즈이다.

설명

가장긴 증가하는 부분수열 길이랑, 그 길이의 원소를 뽑아내는 것이다.

원소를 뽑아내야하기에 해당 수열위치를 알려주는 배열도 만들면서

매번 가장 긴 부분 위치가 갱신될때마다 수열위치 저장하느 배열에 참조 했던 위치를 저장하는 식으로 나아가야한다

주의

헷갈렸던 것이 있는데 MEMSET으로 왜 B를 -1로 했을까?.. 고민했다가 필요없나 싶었는데
지우니 오류가 발생한다

밑에 이유를 확인하고자 내가 코드가 안보여서 주위에 질문을 구하니
while에서 탈출 조건을 보라고한다.. 아하 이해 끝!

소스

#include <bits/stdc++.h>

using namespace std;

int n, maxidx;
int a[1001];
int b[1001]; //k일때 가장 긴 길이 넣고 그때의 인덱스 i를 넣자 
int dp[1001];

int solve(int idx) {

    if (dp[idx] != -1) return dp[idx];

    dp[idx] = 1;

    for (int i = 1; i <= idx; i++) {
        if (a[i] < a[idx] && i < idx) {
            //dp[idx] = max(solve(i) + 1, dp[idx]);
            if (solve(i) + 1 > dp[idx]) {
                dp[idx] = solve(i) + 1;
                b[idx] = i;  것이 i
            }

        }
    }
    return dp[idx];
}
int main() {

    cin >> n;

    for (int i = 1; i <= n; ++i) cin >> a[i];
    memset(dp, -1, sizeof(dp));

    memset(b, -1, sizeof(b));
    int ans = 0;

    for (int i = 1; i <= n; ++i) {
        if (ans < solve(i)) {
            ans = solve(i);
            maxidx = i;

        }
    }

    vector<int> v;

    while (maxidx >= 0)
    {
        v.push_back(a[maxidx]);
        maxidx = b[maxidx];
    }

    cout << ans << endl;

    for (int i = v.size() - 1; i >= 0; i--) cout << v[i] << " ";

    return 0;
}