[백준 / BOJ] C++ 2568 전깃줄 - 2

2568번: 전깃줄 - 2

 

문제

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

2568번: 전깃줄 - 2

 

 

풀이

전깃줄 문제는 이어진 두 지점이 입력으로 들어오기 때문에 pair로 받아 저장한다. A 건물 기준으로 1번부터 이어야 하기 때문에 입력받은 값들을 정렬한다. 그리고 N의 크기가 10^5이기 때문에 시간복잡도가 O(N^2)인 알고리즘으론 시간초과가 나게 된다. 따라서 시간복잡도가 O(NlogN)인 알고리즘을 사용해 14003번 문제와 같이 가장 긴 증가하는 부분 수열(LIS)을 구할 수 있다.

[14003번 가장 긴 증가하는 부분 수열 5 문제] | [14003번 가장 긴 증가하는 부분 수열 5 풀이]

 

이 문제에선 없애야 하는 전깃줄을 출력하는 것이므로 LIS에 포함되는 수들(즉, 뒤에서부터 찾은 수들)을 idx 배열에서 값을 0으로 해준다. 그리고 값이 0이 아닌 인덱스의 이어진 줄을 출력하면 된다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  vector<pair<int, int>> v(n);
  vector<int> LIS, idx(n);
  for (int i = 0; i < n; i++)
    cin >> v[i].first >> v[i].second;
  sort(v.begin(), v.end());
  LIS.push_back(v[0].second);
  idx[0] = 1;
  for (int i = 1; i < n; i++) {
    if (LIS.back() < v[i].second) {
      LIS.push_back(v[i].second);
      idx[i] = LIS.size();
    } else {
      auto it = lower_bound(LIS.begin(), LIS.end(), v[i].second);
      *it = v[i].second;
      idx[i] = it - LIS.begin() + 1;
    }
  }
  int size = LIS.size();
  cout << n - size << '\n';
  for (int i = n - 1; i >= 0; i--)
    if (idx[i] == size) {
      idx[i] = 0;
      size--;
    }
  for (int i = 0; i < n; i++)
    if (idx[i])
      cout << v[i].first << '\n';
  return 0;
}