[99클럽/코딩테스트 챌린지/C++] 가장 큰 증가하는 부분 수열 문제 해결

문제 링크

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

 

📝 문제 요약

문제: 주어진 수열에서 순서를 유지하면서 숫자가 점점 커지는 부분 수열 중, 합이 가장 큰 부분 수열의 합을 구하는 문제.

입력:

• 수열 크기 N (1 ≤ N ≤ 1,000)
• 수열 A (1 ≤ Ai ≤ 1,000)

출력: 가장 큰 증가하는 부분 수열의 합.

📌 접근법

1. DP 배열 정의

• dp[i]: i번째 숫자를 마지막으로 하는 가장 큰 증가 부분 수열의 합을 저장합니다.

2. 점화식

• 조건:
  arr[j] < arr[i] (j < i)인 경우, arr[j]를 arr[i] 앞에 추가할 수 있습니다.
• 점화식:
  dp[i] = max(dp[i], dp[j] + arr[i])

3. 초기화

• 각 숫자는 혼자만으로 합이 되는 증가 부분 수열을 만들 수 있으므로, dp[i] = arr[i]로 초기화합니다.

4. 결과 계산

• DP 배열을 모두 계산한 후, 가장 큰 값이 가장 큰 증가 부분 수열의 합입니다.

전체 코드

// ConsoleApplication1.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;


int main()
{
    int N = 0;
    std::cin >> N;
    vector<int> arr = vector<int>(N);

    for (size_t i = 0; i < N; i++)
    {
        std::cin >> arr[i];
    }
    vector<int> dp = vector<int>(N);
    for (int i = 0; i < dp.size(); i++)
    {
        dp[i] = arr[i];
        for (int j = i; j >= 0; j--) {
            if (arr[j] < arr[i]) {
                dp[i] = max((dp[j] + arr[i]),dp[i]);
            }
        }
    }

    int answer = *max_element(dp.begin(), dp.end());

    std::cout << answer << '\n';

    return 0;
}

📌 배운 점

1. 동적 계획법(DP)의 활용: 이전 상태를 기반으로 현재 상태를 최적화하는 점화식을 구성하여 문제를 해결할 수 있었습니다.
2. 점화식 설계: dp[i] = max(dp[i], dp[j] + arr[i])라는 점화식은 문제의 요구 사항(최대 합)을 명확히 반영했습니다.
3. 초기화와 조건의 중요성: 각 dp[i]를 초기화할 때, arr[i]를 직접 할당하는 것이 문제 해결의 핵심이었습니다.
4. 시간 복잡도: 이중 반복문을 사용했으므로 시간 복잡도는 **O(N²)**이지만, 문제의 입력 크기 제한(N ≤ 1000)에서는 충분히 효율적입니다.

📌 느낀 점

이번 문제를 통해 "부분 수열"의 합을 다루는 방법을 명확히 이해하게 되었습니다. 특히, DP 배열의 의미를 올바르게 정의하고 점화식을 세우는 것이 문제 해결의 핵심임을 다시 한번 깨달았습니다.

향후 더 큰 입력에 대비해 이분 탐색을 사용한 최적화 등 고급 알고리즘으로 접근해보고 싶습니다.