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

2352번: 반도체 설계

접근 방법

연결선이 꼬이면 안되기 때문에, 가장 긴 증가하는 부분 순열 (LIS) 알고리즘을 사용하기로 결정

이때 dp로 접근하게 되면 시간 복잡도가 O(n^2)이기에 시간 초과가 발생했다.

여기에서는 시간 복잡도를 O(n log n)으로 줄이기 위해서 이분탐색을 이용하기로 결정한다.

vector<int> v(n) -> 연결되어야 하는 포트 번호들을 입력받는 배열
vector<int> dp -> 증가하는 부분 수열에 들어갈 수를 최적의 값으로 유지하기 위한 배열
int pos -> 반복문을 거치는 현재 원소(v[i])가 dp에 들어갈 위치를 결정하는 역할을 한다.
같은 숫자는 존재하지 않기에 binary_search 함수를 구현, dp에 들어갈 위치를 이분 탐색으로 결정, 반환하는 값(ans)이 dp의 사이즈와 같다면 추가

코드

#include <iostream>
#include <vector>

using namespace std;

int binary_search(vector<int> &dp, int target) {
    int lft = 0, rgt = dp.size() - 1;
    int ans = rgt + 1;

    while (lft <= rgt) {
        int mid = (lft + rgt) / 2;
        if (dp[mid] > target) {
            ans = mid;
            rgt = mid - 1;
        } else {
            lft = mid + 1;
        }
    }

    return ans;
}

int main() {
    int n;
    cin >> n;

    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];

    vector<int> dp;

    for (int i = 0; i < n; i++) {
        int pos = binary_search(dp, v[i]);
        if (pos == dp.size()) dp.push_back(v[i]);
        else dp[pos] = v[i];
    }

    cout << dp.size();

    return 0;
}