백준 11055 가장 큰 증가 부분 수열

algorithm : dp

 

해설

이문제는 dp 중에서도  LIS문제이다.

dp [i] 정의 : 배열 i번째 까지 arr [i]를 사용했을 때 최댓값

 

dp[1]에서 오는 경우와 dp [3]에서 오는 경우가 있다 이경우 중 더 큰 값에 arr [6]을 더하면 dp [6]이 된다

LIS경우 이문은 N <= 1,000 이하이기 때문에 N ^ 2 풀이가 가능하지만 N이 10,000 이상이면 시간 초과가 날 수 있다

LIS는 O(N long N)까지 줄일 수 있다 이 방법은 다른 풀이에서 다룬다

https://tedcho.tistory.com/32 참고

 

소스코드

#include<bits/stdc++.h>
#define LM 1000+10
#define INF 199999999
using LL = long long;
using namespace std;

int N;
int arr[LM],dp[LM];
int ans;

void input(){
    scanf("%d",&N);
    for(int i =  1 ; i <= N ; i++)
        scanf("%d",&arr[i]);
}

void DP(){
    for(int i = 1 ; i <= N ; i++){
        for(int j = 0 ; j < i ; j++){
            if(arr[j] < arr[i])
                dp[i] = max(dp[i],dp[j] + arr[i]);
        }
        ans = max(ans,dp[i]);
    }
    printf("%d",ans);
}

int main(){
    //freopen("input.txt","r",stdin);
    input();
    DP();
    return 0;
}