Computer Science & Engineering

https://www.acmicpc.net/problem/11053

풀이

    문제는 간단하다 수열이 주어졌을 때 수열의 순서를 바꾸지 않고 증가하는 부분 수열로 가장 긴 길이를 출력하는 문제이다.

이 문제는 DP를 이용하여 풀 수 있다. 이 알고리즘을 DP를 이용하여 해결하는 데에는 O(n^2)의 시간 복잡도를 가진다. 브루트 포스 방식으로 i번째 인덱스부터 끝까지 증가하는 수열의 길이를 찾고 가장 긴 길이를 출력하면 된다.

소스 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MN = 1001;

int dp[MN];
int arr[MN];

int main() {
    int N; cin >> N; //길이 입력
    int res = 0; //최대 길이 저장

    for(int i = 0; i < N; i++) //수열 입력
        cin >> arr[i];

    for(int i = 0; i < N; i++) { //i번째 인덱스까지
        dp[i] = 1; //원소 1개의 길이는 1
        for(int j = 0; j < i; j++) { //i번째 인덱스까지
            if(arr[i] > arr[j]) { //증가하는 수열이면
                dp[i] = max(dp[i], dp[j] + 1); //i번째 인덱스까지 최대길이 갱신
            }
        }
        res = max(res, dp[i]); //최대 길이 저장
    }

    cout <<res;
}

이 문제는 dp를 이용하여 i번째 인덱스까지 만들어지는 수열 중 증가하는 수열의 최대 길이만 갱신하는 방식이다. 이 방법의 아쉬운 점은 가장 긴 증가하는 부분 수열 자체를 구할 수는 없다. 또 이 알고리즘은 O(n^2)의 시간 복잡도를 가지는 것이 굉장히 아쉬운 부분이다. 다른 방식을 사용하면 O(N * log N)으로 해결할 수 있다. 이 방식은 가장 긴 증가하는 부분 수열 2에서 다루도록 하겠다.