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

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

문제
수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다.

---

입력 1
6
10 30 10 20 20 10

출력 1
3

---

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

#define MAX 1001

int main() {
  int N, maxval;
  int num[MAX] = {0,};
  int dp[MAX] = {0,};
  int sorted[MAX] = {0,};

  scanf("%d", &N);
  for(int i = 1; i <= N; i++)
    scanf("%d", &num[i]);
  maxval = *max_element(num + 1, num + MAX);

  for(int i = 1; i <= N; i++) {
    dp[i] = *max_element(sorted + num[i] + 1, sorted + maxval + 1) + 1;
    sorted[num[i]] = dp[i];
  }

  printf("%d\n", *max_element(dp + 1, dp + MAX));
}

11053번 가장 긴 증가하는 부분 수열에서 조금만 바꾸면 됐다. 이전에는 dp[i]에 *max_element(sorted + 1, sorted + num[i])였던 부분에서 범위를 sorted + num[i] + 1, num의 가장 큰 원소 + 1로 바꿨다. 그러니까 0 ~ 현재 숫자를 현재 숫자 + 1 ~ 가장 큰 숫자로 바꾼 것이 되겠다.