(SWEA c++)3307. 최장 증가 부분 수열

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBOKg-a6l0DFAWr&categoryId=AWBOKg-a6l0DFAWr&categoryType=CODE

SW Expert Academy

DP 알고리즘을 이용한 문제 풀이.

최장 증가 부분 수열에 관한 내용은 아래 블로그에 설명이 잘 되어 있으므로 참고..!

jason9319.tistory.com/113

[최장 증가 수열] LIS(Longest Increasing Subsequence)

n의 수가 1000이 최대이므로 간단한 dp 방법으로 풀어도 시간은 초과 되지 않는다..!

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

using namespace std;

int main(void)
{
    int t;
    cin >> t;
    
    for(int tc = 1; tc <= t; tc++)
    {
        int n;
        vector<int> v;
        vector<int> dp(1000, 0);
        cin >> n;
        
        for(int i = 0; i < n; i++)
        {
            int tmp;
            cin >> tmp;
            v.push_back(tmp);
        }
        
        for(int i = 0; i < n; i++)
        {
            if(dp[i] == 0)
                dp[i] = 1;
            for(int j = 0; j < n; j++)
            {
                if(v[j] < v[i])
                {
                    if(dp[i] < dp[j] + 1)
                        dp[i] = dp[j] + 1;
                }
            }
        }
        cout << "#" << tc << " " << *max_element(dp.begin(), dp.end()) << endl;
    }
    return 0;
}