[백준 11053] 가장 긴 증가하는 부분 수열

가장 쉬운 LIS

이진탐색으로 위치 찾아서 넣어주고

맨 끝 위치에 들어가야할때는 v.push_back 해주는게 가장 빠르긴 한데 dp 연습 겸 dp로 품

 

---

#include <iostream>
#include <vector>
#include <algorithm>

#define SIZE 1001

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N;
    vector<int> v;

    int dp[SIZE] = {
        0,
    };

    cin >> N;

    int x;
    v.push_back(0);
    for (int i = 0; i < N; i++)
    {
        cin >> x;
        v.push_back(x);
    }

    dp[0] = 0;
    for (int i = 1; i <= N; i++)
    {
        // 전 dp랑 비교해서 최신화
        for (int k = 0; k < i; k++)
        {
            if (v[i] > v[k])
            {
                dp[i] = max(dp[i], dp[k] + 1);
            }
        }
    }

    // for (int i = 0; i <= N; i++)
    // {
    //     cout << dp[i] << " ";
    // }
    // cout << "\n";
    int ans = 0;
    for (int i = 0; i <= N; i++)
    {
        ans = max(ans, dp[i]);
    }

    cout << ans;
    return 0;
}