[11722번] 가장 긴 감소하는 부분 수열(DP)

가장 긴 감소하는 부분 수열 성공

 

문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

 

문제접근법.

1. 하나의 원소를 기준으로 가장 긴 문자열을 찾아야 한다.

2. 반복적으로 특정 원소를 기준으로 한 연산이 없도록 한다.(메모이제이션)

 

 앞선 코드와 비슷하지만, 재귀함수 호출없이 문제를 풀 것이다. DP[i]는 해당 인덱스(i)에서 시작해서 가장 길게 만들 수 있는 값을 저장한다. 다음과 같은 재귀식을 만들 수 있다.

 

 DP[i]를 정의하는 것이 가장 중요하다. 처음에, DP[i]를, i에서 시작한 가장 긴 수열의 길이가 아니라, i까지 포함한 가장 긴 수열로 정의했었다. 이렇게 정의하면 문제가 풀리지 않는다. 예를 들어,

 

 DP[a], DP[b](b = a + 1 ~ N)이라고 가정하자.

DP[b]를 이용해서, DP[a]를 얻을 수 없다. DP[b]는 b ~ N까지 가장 긴 수열을 포함하므로, 이전처럼 원소간의 관계로 DP를 정의할 수 없게 된다.

 

해설코드(C++)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
int dp[1001];
int arr[1001];
int N;
int result = 1;
 
int main(void) {
    freopen("input.txt", "r", stdin);
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
 
    // DP
    dp[N] = 1;
 
    for(int i = N - 1; i >=1 ; i--){
        dp[i] = 0;
        for (int j = i + 1; j <= N; j++) {
            if (arr[i] > arr[j])
                dp[i] = max(dp[i], dp[j]);
        }
        dp[i] += 1;
        result = max(result, dp[i]);
    }
 
    cout << result << endl;
}