[C++/python/11053] 백준 LIS문제

n^2의 시간복잡도를 갖는 코드.

 

C++

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

using namespace std;
int n;
vector<int> arr;
vector<int> dp;

bool comp;

int solution() {
    for(int i=0; i<n; i++){
        for(int j=0; j<i; j++){
            if(arr[i]> arr[j]){
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
    }
    sort(dp.begin(), dp.end());
    return dp[n-1];
}

int main(){
    scanf("%d", &n);
    int element;
    for(int i=0; i<n; i++){
        cin >> element;
        arr.push_back(element);
        dp.push_back(1);
    }
    printf("%d\n", solution());
}

 

 

python

x = int(input())

arr = list(map(int, input().split())) #input을 slice해서 list에 담기

dp = [1 for i in range(x)] # dp 배열 생성

for i in range(x):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))