[백준OJ] 11722번 가장 긴 감소하는 부분 수열

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

11722번: 가장 긴 감소하는 부분 수열

---

 

-풀이-

dp를 이용했다.

dp[i]=k 라고 한다면, i번째 원소가 끝부분인 부분수열의 최대길이라 가정했을때, 가장 긴 감소하는 부분수열의 길이를 K라고 한다는 의미이다.

예를들어 A={10,30,10,20,20,10} 일때,

dp[0]= 10 하나이므로 1

dp[1]= {10,30} 이므로 만들 수 있는 감소하는 부분수열중, 끝이 30인 감소하는 부분수열은 30이되므로, 1이된다.

dp[2]={10,30,10} 이므로 만들 수 있는 감소하는 부분수열중, 끝이 10인 감소하는 부분수열은 10이 되므로, 1이 된다.

dp[3]={10,30,10,20} 이므로 만들 수 있는 감소하는 부분수열중, 끝이 20인 감소하는 부분수열은 30 20 이 되므로, 2가 된다.

 

규칙이 보일것이다.

dp[i]의 값을 구하기 위해선, 0~i까지 돌면서(그 위치를 j라고하자), j에 위치한 숫자가 현재 i번째 위치의 원소의 값보다 크다면, 감소하는 부분수열을 만들 수 있다. dp[j]가 j에 위치한 숫자까지 감소하는 부분수열의 최대길이이므로, dp[i]=dp[j-1]+1 이 된다. 이를 이용해서 문제를 해결하면된다.

그런뒤, 마지막으로 dp값을 정렬 후 , 가장 큰 값을 출력해주면 된다.

 

-시간복잡도-

O(N²)

 

-코드-

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

int dp[1001]={0};
int n;
int arr[1001];

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    
    
    for(int i=0;i<n;i++){
        dp[i]=1;
        for(int j=0;j<=i;j++){
            if(arr[i]<arr[j]){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    sort(dp,dp+n);
    cout<<dp[n-1];
}