[코드트리 챌린지] 4주차 DP l - 조건에 맞게 선택적으로 전진하는 DP / 최대 증가 부분 수열

 

https://www.codetree.ai/missions/2/problems/longest-increasing-subsequence/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드:

#include <bits/stdc++.h>
using namespace std;

int n;
int arr[1005];
int dp[1005]; 
// dp[i]는 마지막으로 고른 원소가 i번째 일때
// 최대 증가 부분 수열을 말합니다.

void Initialize() {
    // 모든 지점이 수열의 시작이 될 수 있으므로
    // 모두 1로 초기화 합니다.
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

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

    Initialize();

    int maxCnt = INT_MIN; // 최대 증가 부분 수열 길이

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            // i번째 보다 앞에 있는 원소들 중
            // arr[i] 보다 작은 값인 arr[j]를 찾고
            // arr[j] 를 선택 했을 때의 최장 길이(dp[j]) + 1
            // 한 값이 dp[i]가 됩니다.
            if (arr[j] < arr[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    // 모든 dp를 탐색하여 가장 큰 값을 고릅니다.
    for (int i = 0; i < n; i++) {
        maxCnt = max(maxCnt, dp[i]);
    }
  

    cout << maxCnt;
}

n을 입력받고 0~n까지 arr 배열을 주어진 값으로 초기화합니다.

dp 배열의 경우 dp[i]는 마지막으로 선택한 원소가 i번째 일때 최장 길이 부분 수열을 뜻합니다.
그러므로 Initialize()함수를 통해 dp[i]를 모두 1로 초기화 해줍니다.
기본적으로 어느 부분이든 시작 위치가 될 수 있기 때문입니다.

그 이후 i 보다 작은 j를 통해 arr[j]를 살펴보면서 arr[i]보다 작은 값이 있는지 확인합니다.
만약 arr[j]가 arr[i]보다 작다면 dp[i]의 값은 arr[j]를 선택했을 때 최장 길이(dp[j]) + 1 이라고
할 수 있습니다.

즉 dp[i]의 점화식은 dp[i] = max(dp[j]+1) (0 <= j < n , arr[j] < arr[i]) 입니다.