[C++] 백준 2352번 반도체 설계

LIS문제입니다.

왼쪽의 수들은 정렬되어 있기때문에
오른쪽의 수들도 가장 많이 정렬되어있는 수열을 찾으면
총 몇개를 연결할 수 있는지 알 수 있습니다.

(n^2 = 시간초과)
40000^2으로 1,600,000,000의 처리가 발생합니다.
1초에 약 1억번의 처리밖에 처리하지 못하기 때문에 logn의 방식을 사용해야합니다.

lower Bound함수를 사용해서 logn번의 처리로 해결할 수 있습니다.

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

int main(int argc, char *argv[])
{
  int n = 0;
  int len = 1;
  int arr[40010];
  int DP[40010] = {0};
  scanf("%d", &n);

  for (int i = 1; i <= n; ++i)
  {
    scanf("%d", &arr[i]);
  }

  DP[len] = arr[1];

  for (int i = 2; i <= n; ++i)
  {
    if (DP[len] < arr[i])
    {
      DP[++len] = arr[i];
    }
    else
    {
      int index = lower_bound(DP + 1, DP + len + 1, arr[i]) - DP;
      DP[index] = arr[i];
    }
  }

  printf("%d\n", len);

  return 0;
}