[백준] 줄세우기 2631번 (c++) LSB

출처 : https://www.acmicpc.net/problem/2631

풀이 방법

LSB알고리즘을 사용해서 전체 학생 수에서 LSB를 빼주면 된다.

 

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> students;
vector<int> dp;

int binary_search(int target) { // 타겟을 찾음 
    int left = 0, right = dp.size() - 1;
    int mid = (left + right) / 2;
    while(left <= right) {
        mid = (left + right) / 2;
        if (dp[mid] == target) {
            return mid;
        }
        else if (dp[mid] < target && dp[mid+1] > target) {
            return mid+1;
        }
        else if (dp[mid] > target) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    } 
    return mid;
}

void lsb() { // 최소 증가 부분 수열
    dp.push_back(students[0]);

    for (int i = 1;i < N;i++) {
        int lsb_len = dp.size();
        if (dp[lsb_len - 1] < students[i]) { // 마지막 크거나 같으면 추가
            dp.push_back(students[i]);
        }
        else {
            int idx = binary_search(students[i]);
            dp[idx] = students[i];
        }
    }
}

int main() {
    cin >> N;
    for (int i = 0;i < N;i++) { // 입력 받기
        int number;
        cin >> number;
        students.push_back(number);
    }
    lsb();
    cout << N - dp.size() << endl;
    return 0;
}