백준 11055 c++ "가장 큰 증가하는 부분 수열" -PlusUltraCode-

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

 

 

[필자 사고]

가장 긴 부분수열을 체킹하는 방법 => 동적프로그래밍이다.필자는 이 문제를 풀기 전에 가장 긴 부분수열의 갯수를 구하는 문제를 풀었다.해당 문제와 알고리즘이 비슷하지만 그대는 갯수를 구하는거고 현재는 합을 구하는 문제이다.

상세한 코드 설명은 아래에 적어 놓겠다.

필자가 이 문제를 풀면서 놓친 부분은 dp를 초기화 할때 arr의 모든 idx값으로 초기화 하는게 아니라

0으로 초기화 했다는 문제다.

생각해보니 개개인이 가장 큰 숫자일 수 있기 때문에 dp자체를 초기화 할때 arr의 인덱스로 초기화 해야 된다는것을 알게됐다.

[코드 해설]

1. 입력 처리 (Input 함수)

사용자로부터 정수 N을 입력받아 배열의 크기를 결정한다. 이후, N개의 정수를 입력받아 배열 arr에 저장하며, 동시에 dp 배열도 초기화한다.
dp[i]는 arr[i]까지의 증가 부분 수열 중 가장 큰 합을 저장하는 역할을 하며, 초기에 각 arr[i] 값으로 설정된다.

2. 최대 증가 부분 수열의 합 계산 (Game_Start 함수)

주어진 배열에서 연속하지 않아도 되는 증가하는 부분 수열을 찾고, 그 합이 최대가 되는 값을 계산한다.
먼저, Result를 arr[0] 값으로 초기화한다.
그 후, 배열의 두 번째 원소부터 마지막 원소까지 순회하면서, 현재 원소보다 앞에 있는 원소들 중 더 작은 값이 있는지 확인한다.
만약 arr[i]가 arr[k]보다 크다면, 기존의 dp[i] 값과 dp[k] + arr[i] 중 큰 값을 선택하여 dp[i]를 갱신한다.
이 과정이 끝나면 dp[i] 값들 중 가장 큰 값을 Result에 저장하여 최종적으로 출력한다.

[소스 코드]

 

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

using namespace std;

vector<int> dp;
vector<int> arr;
int N;

void Input() {
    cin >> N;
    dp.resize(N);
    arr.resize(N);

    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        dp[i] = arr[i]; 
    }
}

void Game_Start() {
    int Result = arr[0];

    for (int i = 1; i < N; i++) {
        for (int k = 0; k < i; k++) {
            if (arr[i] > arr[k]) {
                dp[i] = max(dp[i], dp[k] + arr[i]);
            }
        }
        Result = max(dp[i], Result);
    }

    cout << Result;
}

int main() {
    Input();
    Game_Start();
    return 0;
}