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

2352번: 반도체 설계

 

문제

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

2352번: 반도체 설계

 

 

풀이

전깃줄 문제와 같이 이어진 두 포트가 입력으로 들어오기 때문에 pair로 받아 저장한다. 왼쪽 포트 기준으로 가장 많이 이어야 하기 때문에 입력받은 값들을 정렬한 후 2568번 문제와 같은 알고리즘으로 가장 긴 증가하는 부분 수열(LIS)을 구할 수 있다. N의 범위가 4 × 10^4 이므로 시간복잡도가 O(N^2)인 알고리즘으로 풀 수 없고 O(NlogN)인 알고리즘을 사용해 풀어야 한다.

 

[2568번 전깃줄 - 2 문제] | [2568번 전깃줄 - 2 풀이]

 

이 문제에선 2568번 문제와 달리 최대 연결 개수를 출력하는 것이므로 LIS의 길이를 출력하면 된다.

 

 

코드

#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++) {
    int x;
    cin >> x;
    v[i] = {i + 1, x};
  }
  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;
    }
  }
  cout << LIS.size() << '\n';
  return 0;
}