문제

문제 링크

문제 접근

  • 이 문제는 디피 중에도 LIS(가장 증가하는 부분 수열) 문제에서 사용한 방법을 쓸 수 있을 것 같았다.
  • 그래서 최근에 사용해본 nlogn 만에 길이를 찾아내는 방법을 사용해서 정답을 발견했다!

코드

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

namespace fio {
    const int BS = 524288;
    char buf[BS];
    char *p = buf + BS;
    inline char readChar() {
        if (p == buf + BS) {
            fread(buf, 1, BS, stdin);
            p = buf;
        }
        return *p++;
    }
    int readInt() {
        char c = readChar();
        while (c < '0') c = readChar();
        int ret = 0;
        while (c >= '0')ret = ret * 10 + c - '0', c = readChar();
        return ret;
    }
}

int n, arr[40001], cnt;
vector<int> ans;
int main(){
    n = fio::readInt();
    for(int i = 0; i < n; i++)arr[i] = fio::readInt();
    for(int i = 0; i < n; i++){
        if(!cnt || ans[cnt - 1] < arr[i])ans.push_back(arr[i]), cnt++;
        else{
            int pos = lower_bound(ans.begin(), ans.end(), arr[i]) - ans.begin();
            ans[pos] = arr[i];
        }
    }
    printf("%d", cnt);
}

느낀점

  • LIS가 이렇게 활용될 줄 몰랐는데 생각해냈다는 것에 뿌듯했다.
  • nlogn으로 끝낸 것도 너무 만조쿠하다 ㅎㅎ