11055_가장 큰 증가 부분 수열

Concept & Idea

조건은 생각보다 간단하다.
우선 증가하는지 보면되고, dp배열에 여태까지 기록한 가장 큰 증가 부분 수열의 값을 저장해놓으면 된다.
가장 큰 증가 부분 수열을 찾으면, 그 값에 자기 자신을 더한 값을 DP[i]에 저장하면 된다.

Code

#include <iostream>
using namespace std;
int n;
int map[1001];
int dp[1001];
int res=0;
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>map[i];
    }
    for(int i=1; i<=n; i++) {
        int min=0;
        for(int j=0; j<i; j++) {
            if(map[i]>map[j] && min<dp[j]){
                min=dp[j];
            }
        }
        dp[i]=map[i]+min;
        if(res<dp[i])
            res=dp[i];
    }
    cout<<res<<endl;
}

 

Fealing

뭔가.. 다이나믹 프로그래밍으로 꼭 풀어야한다고 하니까 코드에 손대기가 힘든 것 같다.
좀 더 복잡하게 생각하는 것 같기도하고..
규칙을 먼저 찾아보자!