백준 12015 가장 긴 증가하는 부분 수열 2 +a

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

12015번: 가장 긴 증가하는 부분 수열 2

문제 해설

포인트는 다음과 같다.

C[i] = 지금까지 만든 길이가 i인 증가 부분 수열 중 최소 마지막 값

=> C의 인덱스를 LIS의 길이와 연관시키고, 최소 마지막 값을 기록해 둠으로써 해당 값 보다 현재 비교할 수열의 값이 큰 경우 길이 i+1인 부분 수열을 만들 수 있다.

이때, C에 저장된 수는 오름차순으로 정렬된다. >> 정렬된 상태이므로 이분 탐색이 가능하다.

 

#include <iostream>
#define fio cin.tie(0)->sync_with_stdio(0)
using namespace std;

#include <vector>
int main() {
	fio;
	int N; cin >> N;
    vector<int> A(N+1, 0);
    vector<int> L(N+1, 0);
    for(int i=1; i<=N; i++) cin >> A[i];
    vector<int> C; // C[i] = 지금까지 만든 부분 수열이 갖는 길이 i인 증가 부분 수열 중 최소의마지막 값
    C.push_back(0);
    for(int i=1; i < A.size(); i++){
        auto lower = lower_bound(C.begin(), C.end(), A[i]);
        if(lower == C.end()){// C[i]의 원소 중 A[i]보다 크거나 같은 것이 없다.
            C.push_back(A[i]);
            L[i] = C.size()-1;
        }else{
            int idx = lower - C.begin();
            C[idx] = A[i];
            L[i] = idx;
        }
    }

    cout << C.size()-1 <<'\n';
	return 0;
}

 

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

12738번: 가장 긴 증가하는 부분 수열 3

12015번 문제와 99%같은 문제다.

다른 점은 수열 A에 속한 수의 범위이므로 이점만 신경써주면 된다.

#include <iostream>
#define fio cin.tie(0)->sync_with_stdio(0)
using namespace std;

#include <vector>
int main() {
	fio;
	int N; cin >> N;
    vector<int> A(N+1, 0);
    vector<int> L(N+1, 0);
    for(int i=1; i<=N; i++) cin >> A[i];
    vector<int> C; // C[i] = 지금까지 만든 부분 수열이 갖는 길이 i인 증가 부분 수열 중 최소의마지막 값
    C.push_back(-1000'000'001);
    for(int i=1; i < A.size(); i++){
        auto lower = lower_bound(C.begin(), C.end(), A[i]);
        if(lower == C.end()){// C[i]의 원소 중 A[i]보다 크거나 같은 것이 없다.
            C.push_back(A[i]);
            L[i] = C.size()-1;
        }else{
            int idx = lower - C.begin();
            C[idx] = A[i];
            L[i] = idx;
        }
    }

    cout << C.size()-1 <<'\n';
 
	return 0;
}