[백준(BOJ)] 11055번: 가장 큰 증가 부분 수열 (Dynamic Programming, C++)

💻 C++ 제출코드

---

#include <stdio.h>
#include <algorithm>
using namespace std;

int main(){
    int N;
    scanf("%d", &N);
    int A[N] = {};
    int DP[N] = {};

    for(int i=0; i<N; i++) scanf("%d", &A[i]);
    for(int i=0; i<N; i++){
        DP[i] = A[i];
        for(int j=0; j<i; j++){
            if(A[i] > A[j]) DP[i] = max(DP[i], DP[j]+A[i]);
        }
    }

    printf("%d", *max_element(DP, DP+N));
    
}

 

📝 문제풀이 과정

---

• BOJ:11053 과 비슷한 문제인데, 증가하는 부분 수열의 원소의 합에서 최댓값을 구해야 한다.
• DP 배열에서 각 원소에서의 증가하는 부분 수열 최댓값을 저장한다.
• 11053번과 동일하게, i번째보다 작은 인덱스까지의 원소들을 비교해서 더해가는데, DP[i]는 A[i]로 초기값을 준다.
• 그리고 i번째 전까지의 DP[j] + A[i]와 비교해서 더 큰 것을 DP[i]로 준다.

 

 

• 원소가 10 90 20 80 100 인 경우, max(DP[i], DP[j]+A[i])를 처리해줘야 원소가 j == 1인 경우에서 200과 비교했을 때 j == 3인 경우에서 DP[4]인 경우가 210으로 더 크므로 이 210을 DP[4]로 가져간다.

 

 

👏 결과

---