[C++] 백준 11722번 가장 긴 감소하는 부분 수열

다이나믹 프로그래밍 문제입니다.

 

수열이 주어졌을 때 감소하면서, 가장 긴 수열의 길이를 구하는 문제입니다.

 

현재 위치의값이 비교할 값보다 작으면서 

현재 위치에 저장된 값이 비교할 위치의 저장값 보다 작거나 같으면

비교할 값의 위치에 저장된 값 +1 을 현재 위치의 저장값에 넣습니다.

 

코드로 보면 다음과 같습니다.

if (num[i] < num[j] && memo[i] <= memo[j]) {
   memo[i] = memo[j] + 1;
}

 

#include <iostream>
#include <algorithm>
using namespace std;

int main(int argc, char *argv[])
{
   int memo[1010] = { 1, };
   int num[1010] = { 0, };
   int result = 0;
   int n;
   cin >> n;

   for (int i = 1; i <= n; ++i) {
      cin >> num[i];
      memo[i] = 1;
      for (int j = i - 1; j > 0; --j) {
         if (num[i] < num[j] && memo[i] <= memo[j]) {
            memo[i] = memo[j] + 1;
         }
      }
   }

   for (int i = 1; i <= n; ++i) {
      result = max(result, memo[i]);
   }
   cout << result << endl;

   return 0;
}