[백준/Baekjoon] 11055 가장 큰 증가하는 부분 수열 C++ :: Dynamic programming

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

11055번: 가장 큰 증가하는 부분 수열

---

1. Logic

0~n-1까지 순회하면서 각 시작 위치보다 큰 숫자만 더해주면서 최댓값을 구해주면 된다.

코드를 보면 이해가 쉬울 것 이다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

int n;

vector<int> input;

//증가하는 부분수열의 합
int dp[1001][1001];

int solve(int idx, int choice) {
    if(idx == n) return 0;
    
    int &ret = dp[idx][choice];
    
    if(ret != -1) return ret;
    ret = 0;
    
    if(input[idx] > choice) {
        ret = max(ret, solve(idx+1, input[idx]) + input[idx]);
    }
    
    ret = max(ret, solve(idx+1, choice));
    
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(dp, -1, sizeof(dp));
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        
        input.push_back(a);
    }
    
    int ans = 0;
    
    for(int i = 0; i < n; i++) {
        ans = max(ans, solve(i, 0));
    }
    
    cout << ans;
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90