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

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

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

8943

5611

4608

64.828%

문제

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

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

 

문제접근법.

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

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

 

해설코드(C++)

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

 

이 문제가 이해되지 않는다면, 다이나믹 프로그래밍 기본 문제들을 확인하면서 이해도를 높이도록 노력한다.