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

문제 링크 : https://www.acmicpc.net/problem/11053

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("test.txt", "rt", stdin);
    int n;
    cin >> n;
    vector<int> arr(n + 1,0);
    vector<int> dp(n + 1,0);
    for(int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        int idx = 0;
        for(int j = 1; j <= i; j++)
        {
            if(arr[i] > arr[j])
            {
                idx = max(idx,dp[j]);
            }
        }
        dp[i] = idx + 1;
        ans = max(ans,dp[i]);
    }
    cout << ans;
    return 0;
}

웰노운으로 알려진 LIS 알고리즘 문제이다.

문제의 예시를 통해 알고리즘을 표현하면
0,10,20,10,30,20,50이 초기 상태의 arr 배열이고(일부러 앞에 0 한칸을 추가했다)
0,0,0,0,0,0,0이 초기 상태 dp이다.

첫 내부 for문에서 idx 변수는 0인 상태, i는 1이고 j는 1~i(현재 1) 까지 탐색한다

이 상태에서 arr[i] 값이 arr[j](인덱스 i보다 작은 모든 arr의 구간을 탐색) 보다 크다면 arr[i] 는 arr[j] 다음 값으로 증가하는 부분 수열의 값이 될 수 있는 후보값이다.

하지만 우리가 구하려고 하는 것은 최장 길이 증가 부분수열이므로, dp[j]의 값과 현재 idx값 중 더 큰 값을 idx에 저장한다.

내부 for문이 끝난 후 idx에는 dp[i - 1]까지 탐색한 값들 중 가장 긴 부분수열의 값이 저장되어 있을 것이다. 따라서 dp[i]는 idx + 1을 저장하여 dp[i]는 가장 긴 부분수열에 포함되었을 때 idx + 1의 길이가 나온다 라는 것을 저장한다.

답은 외부 for문이 모두 작동한 후 dp 배열에서 가장 큰 수가 된다.