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

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

LIS(Longest Increasing Subsequence) 라는 유형이라고 한다.

태어나서 처음 들어본 유형이었고…DP로 분류가 되어 있었기에 단순한 DP만 생각중이었다.

사실, LIS는 풀이 방법이 두 가지가 있다고 한다. 첫 번째는 DP이고, 두 번째는 이진탐색이라고 한다.

이번 포스트에서는 DP로 해결하는 방법을 먼저 소개해볼까 한다.

우선, 문제에서 요구하는 것은 주어진 수열에서 가장 길게 증가하는 부분 수열을 구하는 것이다.

DP로 해결하는 방법은 가장 간단한 해결 방법이다.

우선 수열의 맨 처음의 상태를 1로 둔다. 이제 여기서 한 번 증가할 때마다 이 상태도 1씩 증가한다.

한 칸씩 인덱스를 오른쪽으로 옮겨가며, 자신보다 왼쪽에 있는 모든 수들을 본다.

만약 자신의 왼쪽에 자신보다 작은 숫자들이 있다면, 그 중에 가장 큰 상태를 가지고 있는 숫자를 선택한다.

가장 큰 상태를 가지고 있다는 것은 자신보다 작은 숫자들 중에서는 가장 큰 숫자인 것과 동일하다.

따라서 해당 숫자 (자신보다 작은 숫자들 중에서는 가장 큰 숫자)의 상태에 + 1을 하여 자신의 상태를 설정하면 된다.

수열의 끝까지 간 경우에는 저장한 상태들 중에서 가장 큰 것을 출력한다.

#include <iostream>

using namespace std;

int main(){
    int N;
    int arr[1005];
    int dp[1005];
    cin >> N;
    
    for(int i=1;i<=N;i++){
        cin >> arr[i];
    }
    dp[1] = 1;
    int answer = 0;
    for(int i=2;i<=N;i++){
        int tmp = 0;
        for(int j=1;j<i;j++){
            if(arr[i] > arr[j]){
                if(dp[j] > tmp) tmp = dp[j];
            }
        }
        dp[i] = tmp + 1;
    }
    for(int i=1;i<=N;i++){
        if(dp[i] > answer) answer = dp[i];
    }
    cout << answer;
}

코드를 보면 알겠지만, 시간복잡도가 O(N^2) 이다. 이번 문제에서는 N이 작았기 때문에 가능했지만, 크다면 다른 방법을 생각해봐야 한다.