[백준/C++] 11053번: 가장 긴 증가하는 부분 수열(S2)

문제

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

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

가장 긴 증가하는 부분 수열을 Longest Increasing Sequence (LIS)라고 부른다.

LIS문제를 
DP로 풀면 O(N^2),
lower_bound로 풀면 O(NlogN),
segment tree로 풀면 O(NlogN) 이다.

이 문제는 1 ≤ N ≤ 1,000 이므로 DP를 이용해 풀어보려한다.

 

 

사용한 알고리즘

2022.01.19 - [PS/Algorithm] - [알고리즘 개념정리] 3. 동적계획법(DP)

 

 

풀이

배열 arr에는 수열 A를 저장하고,
dp[i]에는 dp[i]로 끝나는 LIS의 길이를 담아줄 것이다.

n=9인 상황 예시
i    0   1   2   3   4   5   6   7   8
arr  5  20  17  12  15  30   18  22  6
dp   1   2   2   2   3   4   4   5   2

arr[i]보다 앞에 있는 수들 중 크기가 arr[i]미만인 수들 중에
(MAX dp[j])+1이 dp[i]이다.

위에서 만약 dp[7]을 구한다고 해보자.
arr[7]보다 앞에 있는 수들 중 arr[7] (=22)보다 작은 수들을 찾는다.
그중에 dp값이 가장 큰 것은 dp[6] =4이다.
따라서 dp[7] =dp[6]+1 =5이다.

 

 

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;

int arr[1001]; //수열A저장
int dp[1001]; //dp[i]는 dp[i]로 끝나는 LIS길이

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    dp[0]=1;

    int n,ans=1; cin>>n;
    for(int i=0; i<n; i++) cin>>arr[i];

    for(int i=1; i<n; i++){
        int dpMAX=0;
        for(int j=0; j<i; j++){
            if(arr[j]<arr[i]) dpMAX= max(dpMAX, dp[j]);
        }
        dp[i]=dpMAX+1;
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}