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

문제

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

 

 

풀이

단순한 DP 문제였다!

 

나는 숫자를 입력받는 배열과 DP 배열의 첫 번째 원소의 값을 0으로 저장해놓고, 1번 index부터 값을 저장할 수 있도록 하기 위해 n+1 크기의 배열을 이용하였다.

( 이렇게 하면 최솟값을 저장하고~ 이런 과정을 거칠 필요가 없어서 좋았다.)

 

 

그리고 현재 숫자 이전의 숫자들 중 현재 숫자보다 더 작은 숫자의 DP값을 비교하면서 현재 숫자의 DP를 갱신해주면 된다.

DP 배열에는 i 번째 숫자까지의 최대 증가 부분 수열의 합이 저장된다.

DP[i] 가 갱신되는 경우는, A[j] < A[i] 이면서 DP[j] + A[i] > DP[i] 인 경우이다.

 

 

그리고 DP 배열에 저장된 값이 바뀔 때마다 현재 갱신되는 값이 저장된 최대 합보다 큰지를 검사하여 최대 합을 업데이트해준다.

max < DP[i] 인 경우, max = DP[i]

 

 

최종적으로 max 값을 출력해주면 된다.

 

이를 구현한 코드는 다음과 같다.

 

 

코드

#include <iostream>
using namespace std;


int main()
{
    int n, max = 0;
    cin >> n;
    
    int A[n+1] = {0};
    int dp[n+1] = {0};
    
    for(int i=1; i<=n; i++){
        cin >> A[i];
    }
    
    for(int i=1; i<=n; i++){
        
        // i번째 숫자와 가장 가까운 더 작은 숫자를 찾음.
        for(int j=i-1; j>=0; j--){
            if(A[i] > A[j] && dp[i] < dp[j] + A[i]){
                
                // 해당 숫자까지의 최대 누적합 현재 숫자에 더함.
                dp[i] = A[i] + dp[j];
                
                // 현재 계산한 누적합이 기존의 최댓값보다 큰 경우, 최댓값 갱신
                if(dp[i] > max){
                    max = dp[i];
                }
            }
        }
    }
    
    cout << max << endl;
    return 0;
}