백준 14003 LIS 5 c++ // LIS 이분탐색 오류수정, LIS 출력하는법

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

1. LIS 오류수정

이전문제는  Ai가 1부터시작하기 때문에

if(lis[idx]==0) 이 해당 num이 처음등장하는 개큰수임 과 필요충분조건이 된다

하지만, Ai에 0이 있는경우 이 '0'이 처음등장한다는 의미인지 lis안에 계산된 '0'이 라는 의미인지 불명확하다!!!

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

따라서, if(idx == len) 이렇게 하는것이 Ai의 범위에 상관없이 처음등장하는 개큰수라는 것과 필요충분조건이다!!

//lb 성질에 의해 없는수를 찾으면 v.end()==len를 반환함!!

 

예시) lis : -2 0 0 5

에서 -1삽입시 lis[idx]==0이고, len+1이된다.

하지만, len증가없이 0이 -1로 교체되는게 맞다.

결론 : idx==len 조건을 사용하자!

이것땜에 저녁도못먹고 3시간날림.......ㅅㅂ

gpt가 goat인듯하다. 

괜히 구글링, 백준 질문게시판 뒤져보다가 ㅜㅜ

 

2.  LIS 수열출력하는법

결론부터말한다.

1. index_arr배열을두고, arr[3]=1 : 원본3번이, lis에서 1번임을 뜻한다.

2. 역순으로 뒤에서부터 탐색한다.

len-1 과 같은지 탐색한다.

 

3. 설명

1. 이전게시물 https://mini-96.tistory.com/391 

백준 12015 LIS c++ // 이분탐색, LIS nlgn풀이 종결?, 한계

에서 보았듯이, 이분탐색방법은 "길이"만을 보장한다.

2. 따라서 추가 정보를 기록해줘야한다.

index_arr배열을두고, arr[3]=1 : 원본3번이, lis에서 1번임을 뜻한다.

우리는 len크기의 lis배열을 만들어야한다.

lis[0]부터 채우려면 매우복잡한데, lis[len-1]뒤부터 채우면 쉽다.

즉, 뒤부터 탐색하면서 배열값==len-1인 값을 찾는다. 

찾았으면 len-1을 -1해주고 ans에 넣는다. 

장점 :  i--되면서 15가 자동으로 패스됨을 알 수 있다!

(왜냐면, [50 30 15] 에서 idx of lis3 ->1->2 이렇게 순서가 뒤죽박죽일수는 없기때문이다. )

ex) [50(3), 30(2), 20(1), 10(첫째0) ]

이후, ans를 거꾸로 출력하면 정상 lis 가 완성된다.

 

#include <bits/stdc++.h>
#define endl "\n";

using namespace std;
typedef long long ll;


ll n, lis[1000000 + 4], len, num;
ll Index_Arr[1000000 + 4]; //index[3]=1 : 원본3번, lis 1번
ll a[1000000 + 4]; //원본배열

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    memset(Index_Arr, -1, sizeof(Index_Arr));

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> num;
        a[i] = num;

        int idx = lower_bound(lis, lis + len, num) - lis;
  
        if (idx == len) len++; 
        lis[idx] = num;

        //lis 배열 찾기위한 로직 추가
        Index_Arr[i] = idx;
        
    }
    cout << len<<"\n";

    /*for (int i = 0; i < n; ++i) {
        cout << Index_Arr[i] << " ";
    }cout << endl;*/

    vector<ll> v;
    int find_idx = len - 1;
    for (int i = n-1 ; i >= 0; --i) { //--i 역순탐색 => 3 2 4 에서 2가 자동 pass됨!
        if (Index_Arr[i] == find_idx) {
            find_idx--;
            v.push_back(a[i]);
        }
    }
    reverse(v.begin(), v.end());
    for (auto i : v) {
        cout << i << " ";
    }   
    return 0;
}