챕터3-13. DP | 문제 풀이3 - (2) 백준 No.11055 : 가장 큰 증가 부분 수열

가장 큰 증가 부분 수열 문제

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

문제요약

수열 A가 주어졌을 때 증가 부분 수열 중에서 가장 수열의 합이 큰 것을 구하는 문제
부분 수열이란?  수열에서 일부를 선택한 수열이다.
ex) A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8}
      합이 가장 큰 증가 부분 수열  A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8}
      => 총 합은 1 + 2 + 50 + 60 = 113

해결 방법

* 바로 이전 문제를 조금 수정해서 풀 수 있다.

 

1. D[N]에 어떤 값을 저장할 것인지 문장으로 정의해줘야한다.

다른 문제에서와 마찬가지로 D에 저장되는 값은 분할된 문제의 해답이다.

즉, D[N] 그 자체가 문제에서 원하는 최종 결과값을 의미하지 않는다.
이런 맥락에서 D[i]를 아래와 같이 정의한 뒤 이들의 최대값을 통해 문제가 원하는 해답을 구할 수 있다.

D[i] = "A[1], A[2], ... , A[i]까지 있을 때, A[i]를 마지막 원소로 포함하는 증가하는 부분 수열로 만들 수 있는 최대 합"

이제 이 정의를 이용하여 max(D[1], D[2], ,,,, D[N])을 구하면 해답을 구할 수 있는 것이다.

 

2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다.
- 점화식을 만들 때는 항상 이전항의 값과 연관지어 만들어야 한다. 그래야 다음항을 연달아 구할 수 있기 때문에.
- 그러면 아래와 같은 점화식이 나올 수 있다.

- D[i] = max(D[1], D[2], ..., D[j]) + A[i] (단, j < i 이며, D[1]~D[j]은 A[j] < A[i] 를 만족하는 것만 해당됨)

 

@ 과정을 좀 더 쉽게 이해할 수 있도록 표로 도식화 한 예시

이제 D[1]~D[10] 값 중에서 가장 큰 값이 문제의 답이되는데 이땐 113이다.

 

3. 다이나믹 프로그래밍 방법을 적용할 수 있는 문제인지 확인 => 1, 2번을 거쳐야 이게 잘 보임.
- 위와 같이 큰 문제를 작은 문제로 쪼갤 수 있으며, 작은 문제도 큰 문제와 같은 방법으로 풀 수 있고, 작은 문제들이 겹친다.
   (Overlapping SubProblem)
- 문제의 정답을 작은 문제의 정답으로부터 구할 수 있으며, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
   (Optimal Substructure)

 

4. 코드구현

이 방법을 사용하면 N개의 칸을 채워야 하고, 한칸 D[i]의 값을 채울 때 A[i]번을 A[1] ~ A[i-1]번과 모두 비교하므로 
시간복잡도는 N * O(N) = O(N^2)이 된다. 따라서 이중 for문 구조가 만들어질 것이라 예상할 수 있다.

<Bottom-up 방식>

(1) 구현
-> 'for문을 이용한 반복문'으로 구현

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> d(n);    
    vector<int> a(n);
    
    for (int i=0; i<n; i++)
        cin >> a[i];

    for (int i=0; i<n; i++) 
    {
        d[i] = a[i];
        for (int j=0; j<i; j++) 
        {
            if (a[j] < a[i] && d[j]+a[i] > d[i])
                d[i] = d[j]+a[i];                 // A[j] < A[i]를 만족하는 d 들 중 최대값 + a[i]이 들어감.
        }
    }
    
    cout << *max_element(d.begin(),d.end()) << '\n';
    return 0;
}

 

(2) 시간복잡도
= for 문의 반복 횟수 

이 방법을 사용하면 N개의 칸을 채워야 하고, 한칸 D[i]의 값을 채울 때 A[i]번을 A[1] ~ A[i-1]번과 모두 비교하므로 
시간복잡도는 N * O(N) = O(N^2)이 된다.