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

문제

문제링크 : https://www.acmicpc.net/problem/11055

풀이전략

1. 그동안 풀었던 증가 부분수열 문제와 같다. 단 여기에서는 합이 큰것을 기준으로 답을 찾으면 된다.
2. 0번부터 넘겨주면 메인에서 함수를 한번만 호출해도 전체를 다 검사할 수 있다.

코드

#include<bits/stdc++.h>

using namespace std;

int N;
int a[1001];
int dp[1001];

int maxIncSeq(int n){
    int&ret = dp[n];
    if(ret != -1) return ret;
    // 이전에 문제들에서 계속 배웠던 전체를 확인하는 것이다. 
    for(int i=n+1; i<=N; i++){
        if(a[i]>a[n]){
            // maxIncSeq(i) + a[i] 를 넘겨줌으로서 합을 구한다.
            ret = max(ret, maxIncSeq(i) + a[i]) ;
        }
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    cin >> N;
    memset(dp, -1, sizeof(dp));
    for(int i=1; i<=N; i++){
        cin >> a[i];
    }
    cout << maxIncSeq(0) + 1 << endl;
    return 0;
}

소감

0번을 넘겨줘서 전체를 확인하는 방법이 좋았다. 또한 이제 실버수준의 부분수열은 다 풀수 있을것같다.!