[BOJ] 11053번 가장 긴 증가하는 부분 수열 c++

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

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

---

입력 1
6
10 20 10 30 20 50

출력 1
4

---

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

#define MAX 1001

int main() {
  int N;
  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]);
  for(int i = 1; i <= N; i++) {
    dp[i] = *max_element(sorted, sorted + num[i]) + 1;
    sorted[num[i]] = dp[i];
  }

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

DP를 위한 배열과 현재 임의의 원소가 가질 수 있는 최대 순서번호를 저장하는 배열을 따로 두었다. 증가하는 수열이기 때문에 정렬된 배열이 필요하다고 생각했다. 그래서 배열의 인덱스가 원소의 크기를 가르키도록 길이가 1001인 1차원 배열을 사용했다.

임의의 원소가 x라면 정렬된 배열을 사용해 1부터 x - 1까지 최댓값을 찾는다. 거기에 1을 더하면 x의 수열 내 위치가 된다.

위의 예제인 10 20 10 30 20 50를 예시로 들어 각 원소를 처음부터 순서대로 보자.
num[1] = 10을 보면, 배열 sorted에서 1부터 9(= 10 -1)까지 최댓값은 0이다. 따라서 dp[1] = 0 + 1, sorted[10] = 0 + 1이다.
num[2] = 20을 보면, 배열 sorted에서 1부터 19(= 20 -1)까지 최댓값은 1이다. 따라서 dp[2] = 1 + 1 = 2, sorted[20] = 1 + 1 = 2이다.
num[3] = 10을 보면, 배열 sorted에서 1부터 9(= 10 -1)까지 최댓값은 0이다. 따라서 dp[3] = 1, sorted[10] = 1이다.
num[4] = 30을 보면, 배열 sorted에서 1부터 29(= 30 -1)까지 최댓값은 2이다. 따라서 dp[4] = 2 + 1 = 3, sorted[10] = 2 + 1 = 3이다.
끝까지 반복하면, dp의 값은 1 2 1 3 2 4가 되므로 가장 긴 증가하는 부분 수열의 길이는 dp의 최댓값 = 4가 된다.