백준 11053 (가장 긴 증가하는 부분 수열) c++

문제

11053번: 가장 긴 증가하는 부분 수열

수열이 주어지면 증가하는 부분수열중 길이가 가장 긴 길이를 구하는 문제입니다.

예를들어 {10, 20, 10, 30, 20, 50} 에서 가장 길이가 긴 수열은 {10, 20, 10, 30, 20, 50} 으로 총 길이가 4입니다.

 

수열 {10, 20, 10, 30, 20, 50} 에서 case를 나누어서 생각해보겠습니다.

1) 먼저 가장 첫번째 수열만 보면 그냥 그대로 '10' 밖에 없으므로 최대 길이는 1이 됩니다. dp[1] =1

2) {10, 20} 에서 보면 지금 선택한 수열은 '20'입니다. '20' 앞에 있는 수열이 '20' 보다 작으므로 

   최대 길이는 dp[1] + 1 = dp[2] = 2 입니다.

3) {10, 20, 10} 에서 보면 지금 선택한 수열은 '10' 입니다. 앞에 있는 수열이 '10' 보다 크므로 최대길이는 

   그냥 dp[3] = 1 입니다.

4) {10, 20, 10, 30} 에서 보면 지금 선택한 수열은 '30' 입니다.  30보다 작은 수열들을 배회 하면서 

   dp[3] = max(dp[3], dp[2, 1, 0] + 1) 같은 점화식이 완성됩니다.

 

이런 유형의 문제는 LIS(Longest Increasing Subsequence) 이므로 알고리즘을 완성하는데 

O(N^2) 과 O(NlogN) 의 시간 복잡도를 가지는데 이번에는 O(N^2)으로 해결하였다.

O(NlogN)도 공부해야할 필요가 있다.

---

전체코드 입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int arr[1001];
int dp[1001];
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
    int cnt = 1;
    for (int i = 1; i <= n; i++) {
        dp[i] = 1;
        for (int j = i - 1; j >= 1; j--) {
            if (arr[i] > arr[j])
                dp[i] = max(dp[i], dp[j] + 1);
            cnt = max(cnt, dp[i]);
        }
    }
    cout << cnt;
    return 0;
}