BOJ 1365 꼬인 전깃줄

1365번: 꼬인 전깃줄 (acmicpc.net)

1365번: 꼬인 전깃줄

 

처음에는 그냥 점화식있는 DP인줄 알았지만, 최장 증가 수열 문제이다.

 

근데 내가 구현할 수 있는 최장 증가 수열은 O(N^2)의 시간복잡도를 가져서 예전에 풀었던 코드를 적용할 수가 없었다.

(이문제의 n은 100000)

 

그래서 어쩔수 없이 시간복잡도가 더 좋은 최장 증가수열 알고리즘을 참고를 했다.

최장 증가 부분 수열 - 나무위키 (namu.wiki)

최장 증가 부분 수열 - 나무위키

 

위키긴 하지만, 동작 원리 참고하여 구현하기 충분했다.

 

아래는 내 제출 코드이다.

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
  int n; scanf("%d",&n);
  vector<int> lis;
  for(int i=0;i<n;i++){
    int t;scanf("%d",&t);
    int idx = lower_bound(lis.begin(), lis.end(), t) - lis.begin();
    if(idx >= lis.size()) {
      lis.push_back(t);
    }
    if(lis[idx] > t) {
      lis[idx] = t;
    }
  }
  printf("%ld\n",n-lis.size());
}