백준 11055번 가장 큰 증가 부분 수열 - C++(cpp) 풀이

---

 

1. dp(idx): idx번째 수로 시작하는 합이 가장 큰 증가 부분 수열의 합
2. dp(idx) = max(arr[idx] + dp(next)) (단, idx < next이고 arr[idx] < arr[next])
3. dp(i)의 최댓값이 합이 가장 큰 증가 부분 수열의 합이다.

 

1. dp(idx): idx번째 수로 시작하는 합이 가장 큰 증가 부분 수열의 합

 dp(idx)를 idx번째 수로 시작하는, 합이 가장 큰 증가 부분 수열의 합이라고 하자.

 

2. dp(idx) = max(arr[idx] + dp(next)) (단, idx < next이고 arr[idx] < arr[next])

 arr[idx] 뒤에는 arr[idx]보다 더 뒤에있으면서 큰 수만 올 수 있으므로 dp(idx) = idx < next이고, arr[idx] < arr[next]인 next들에 대해 arr[idx] + dp(next)의 최댓값이 된다. 이때 arr[idx]뒤에 다른 수가 오지 않고 arr[idx] 하나만 있는 경우도 고려해준다.

 

3. dp(i)의 최댓값이 합이 가장 큰 증가 부분 수열의 합이다.

 모든 경우, 즉 0번째 ~ (N-1)번째 수로 시작하는 합이 가장 큰 증가 부분 수열의 합(dp(i))을 모두 구한 뒤, 그중 가장 값이 큰 경우를 선택하면 된다.

반응형

---

#include <iostream>
#include <string.h>

using namespace std;

int N;
int arr[1001], cache[1001];

// dp(idx): arr[idx]로 시작하는 합이 가장 큰 증가 부분 수열의 합
int dp(int idx) {
    if (idx == N) return 0;
    
    int& ret = cache[idx];
    if (ret != -1) return ret;
    
    ret = arr[idx];
    for (int i=idx+1; i<N; i++) {
        if (arr[i] > arr[idx]) {
            ret = max(ret, arr[idx]+dp(i));
        }
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    memset(cache, -1, sizeof(cache));
    
    cin >> N;
    for (int i=0; i<N; i++) cin >> arr[i];
    
    int ans = 0;
    for (int i=0; i<N; i++) {
        ans = max(ans, dp(i));
    }
    
    cout << ans;

    return 0;
}