[ 백준 11055 ] 가장 큰 증가 부분 수열 (C++)

백준의 가장 큰 증가 부분수열(11055) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 주어진 수열에서 부분수열을 만들어야 하는데, 증가하는 부분 수열이여야 하고, 부분수열의 각 원소들의 합이 최대가

   되는 부분 수열을 찾아야 한다.

   문제를 풀기 전에 백준에 '가장 긴 증가하는 부분 수열(11053)' 이라는 문제가 있는데

   이 문제에 대한 풀이를 먼저 읽고 오는 것을 권장한다.

   왜냐하면 너무나도 비슷한 로직을 가지고 있고, 위의 문제에서 한 부분만 바꾸면 이 문제를 해결할 수 있기 때문에

   이 글을 읽기 전에 위의 문제를 풀어보고 풀이까지 보고 오는 것을 권장한다.

   ( 권장드리는 것 뿐, 반드시 그렇게 해야 하는 것은 아닙니다 ! )

   [ 백준 - 가장 긴 증가하는 부분 수열(11053) 문제 ]

   [ 백준 - 가장 긴 증가하는 부분 수열(11053) 풀이 ]

2) 먼저 본인은 이 문제를 해결하기 위해서 2가지 배열을 사용했다.

   먼저 입력으로 주어지는 수열을 저장하는 Arr[], 최댓값을 저장하는 배열 DP[] 이렇게 1차원 배열 2가지를 사용했다.

   DP[a] = b 의 의미는 "a번 인덱스 까지의 가장 큰 부분 수열의 합은 b 입니다." 이다.

   그렇다면 a번 인덱스에서의 가장 큰 부분 수열을 찾기 전에, 가장 작은 부분 수열의 값은 얼마일까 ??

   바로 Arr[a]일 것이다. { 1, 2, 3, 4, 5 } 라는 수열이 있을 때, DP[2]의 값을 찾는다고 가정해보자.

   가장 큰 부분 수열을 찾기 전에, 가장 작은 부분 수열은, '2' 이 원소 하나로만 이루어진 수열일 것이고 그 값은

   Arr[2]인 2가 된다. 즉 DP[a] 의 초기값은 Arr[a]가 된다는 의미이다.

3) 그렇다면, 본격적으로 문제를 풀어보자. 일단 부분 수열을 찾는 가장 큰 조건은 증가하는 부분 수열이여야 한다는 것이다.

   즉, 우리가 찾고자 하는 해당 인덱스에서의 증가하는 부분 수열을 구하려면, 1번부터 해당 인덱스 까지 증가하면서 비교를

   해줘야 한다는 것이다. 이런식으로 !!

for(int i = 1; i <= N; i++)
{
    DP[i] = Arr[i]                // 설명한 DP[i]의 초기값
    for(int j = 1; j<= N; j++)
    {
        if(Arr[j] < Arr[i]) ~~
    }
}

   또 하나의 조건이 더있다. 우리는 각 원소들의 합이 최대가 되는 수열을 찾아내어야 한다.

   즉, DP[i] < DP[j] + Arr[i] 라는 조건이 더 붙어줘야 한다. 지금 까지의 최댓값 + Arr[i]를 더했을 때, 최대가 된다면

   DP[i]의 최댓값은 DP[j] + Arr[i] 가 될 것이기 때문이다.

4) 이런식으로 DP[1] ~ DP[N]까지의 값을 모두 구해주고, 그 중에서 최댓값을 찾아내면 문제를 해결할 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 1001
using namespace std;
 
int N;
int Arr[MAX];
int DP[MAX];
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> Arr[i];
    }
}
 
void Solution()
{
    int Max = 0;
    for (int i = 1; i <= N; i++)
    {
        DP[i] = Arr[i];
        for (int j = 1; j < i; j++)
        {
            if (Arr[j] < Arr[i] && DP[i] < DP[j] + Arr[i])
            {
                DP[i] = DP[j] + Arr[i];
            }
        }
        if (Max < DP[i]) Max = DP[i];
    }
    cout << Max << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}