[백준OJ] 11055번 가장 큰 증가 부분 수열

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

---

 

-풀이-

DP를 이용하여 풀었다.

dp[i]=k 는 i번째 원소까지 증가하는 부분수열의 합중 가장 큰값이 k라는 의미이다.

N의 값이 1000이하이기 때문에 2중반복문을 사용했다.

 

dp[i]의 값을 구하기 위해선, 0~ i-1 까지의 dp값중, i번째 원소보다 해당 인덱스의 원소값이 작으면서, dp값이 가장 큰 값을 찾아 i번째 원소와 더해주면 된다.

그런뒤, dp배열을 정렬해서 , 가장 큰 값을 찾아주면된다.

 

-시간복잡도-

이중반복문이므로 O(N²)이 된다.

 

-코드-

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

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

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