백준, BOJ, 11055번, 가장 큰 증가 부분 수열 : C++ [CPP]

물론 처음부터 생각은 안나겠지만

가장 DP다운 문제가 아닌가 싶다.

 

항상 N번째 항을 어떻게 구해야할까 생각하면 DP의 답은 나오지만..

항상 생각나는 것은 아니다.

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

 

 

---

 

#맞는 풀이

#include <iostream>
#include <algorithm>

using namespace std;

int N;
int arr[1001];
int dp[1001];
int main(){
    cin >> N;
    
    int ans = 0;
    for(int i = 1; i<=N; i++){
        cin >> arr[i];
    }
    //dp[i] -> arr[i]를 증가 부분 수열의 마지막이라 할 때의 부분 수열의 합.
    //즉, 현재 위치의 값을 더한 것이 dp[i]에 저장됨
    
    //dp[i]채우기
    for(int i = 1; i<=N; i++){
        //dp[j]를 뒤져서 arr[i](현재 위치보다 작은 값 중에서 == arr[j] < arr[i])
        //가장 큰 값을 찾음
        for(int j = 1; j<i; j++){
            if(arr[j]<arr[i]){
                dp[i] = max(dp[i], dp[j]);
            }
        }
        //현재 위치 값 더함
        dp[i] += arr[i];
        ans = max(dp[i], ans);
    }
    
    
    
    cout << ans;
    return 0;
}