소스 코드

#include <iostream>
#include <vector>
#define endl "\n"

using namespace std;

int n; // 돌의 개수
vector<int> h; // 돌의 높이
vector<int> d; // d[i]: i번째를 포함하는 가장 긴 증가수열 크기
vector<int> b; // b[i]: 길이가 i인 인덱스 중 최신값
int maxLen; // 가장 긴 증가수열의 크기

void print(const vector<int>& arr) {
  for (const auto& i : arr) cout << i << " ";
  cout << endl;
}

void init() {
  cin >> n;
  h = vector<int>(n + 1);

  for (int i = 1; i <= n; ++i) {
    cin >> h[i];
  }

  d = vector<int>(n + 1, 0);
  d[1] = 1;

  b = vector<int>(n + 1, 0);
  maxLen = 0;
  b[++maxLen] = h[1];
}

int binarySearch(int l, int r, int target) {
  while (l < r) {
    int mid = l + (r - l) / 2;
    if (b[mid] < target) {
      l = mid + 1;
    }
    else {
      r = mid;
    }
  }

  return l;
}

void solve() {
  if (n == 1) {
    cout << 1 << endl;
    return;
  }
  
  for (int i = 2; i <= n; ++i) {
    if (h[i] > b[maxLen]) {
      b[++maxLen] = h[i];
      d[i] = maxLen;
    }
    else {
      int index = binarySearch(1, maxLen, h[i]);
      b[index] = h[i];
      d[i] = index;
    }
  }

  cout << maxLen << endl;
}

int main(int argc, char** argv) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  init();

  solve();
  
  return 0;
}

해설

1. 동적계획법 문제
   : d[i] = i번째를 포함하는 최장 증가 부분 수열의 길이
2. b 배열 활용
   : b[i] = 최장 증가 부분 수열의 길이가 i인 숫자
3. 이분탐색 활용
   : 1 ~ maxLength에 대하여 num[i] 가 들어갈 위치 탐색