[백준/C++] 14003번 가장 긴 증가하는 부분 수열 5 풀이

문제 해석

---

 

---

문제 풀이

---

우선 수열의 크기가 100만이라서 O(N²) 풀이로는 해결할 수 없다.

dp +이분탐색을 이용한 O(Nlog^N) 풀이 방법이 필요하다. 풀이 방법은 14002번을 풀어보면 알 수 있는데

DP 배열을 1차원으로 사용한다고 생각해보면 될 것 같다.

1. 지금 숫자가 내가 가진 숫자 최대값보다 크다면 배열의 마지막 값으로 추가한다. (코드상 order 배열)
2. 지금 숫자가 최대값보다 작다면 이분탐색을 통해 지금 숫자보다 큰 최소값과 교환해준다.
   • 이 때 1차원 DP의 경우 값을 덮어 씌워가며 계산을 진행하는게 정석인데, 가장 긴 증가하는 부분 수열의 길이를 찾을 때 바뀌어나간 값들의 길이가 최대가 되지 않는 이상 길이 자체에는 영향을 미치지 않는다.
   • 여기까지가 14002번의 문제 풀이다.
3. 그러나 여기서 가장 긴 증가하는 수열을 출력해야하므로 값이 변한 것이 문제가 된다.
   • 그럼 변화시키기 전 어떤 값이 증가하는 수열의 몇번째 순서인지를 배열에 저장하도록 한다.(코드상 record 배열)
   • 순서 값을 record 배열의 뒤에서부터 찾아나가며 증가하는 수열 값을 수정해준다.
     (ex: 1 3 5 2 4 5의 경우 index값이 0 1 2 1 2 3가 되는데 앞에서부터 찾아나가면 1 3 4 5를 찾을 수 없다.)

---

코   드

---

#include <bits/stdc++.h>
using namespace std;

class LIS {
private:
    vector<int> order;
    vector<int> record;
    vector<int> sequence;

public:
    int size;
    
    int record_length() {
        return record.size() - 1;
    }

    int order_length() {
        return order.size() - 1;
    }

    int order_size() {
        return order_length() + 1;
    }

    int change_order_from_seq(int cnt, int idx) {
        order[cnt] = sequence[idx];
        return cnt - 1;
    }

    vector<int> get_order() {
        return order;
    }

    bool is_eqaul_record(int cnt, int idx) {
        return record[idx] == cnt;
    }

    void get_input() {
        for (int i = 0 ; i < size ; i++) {
            cin >> sequence[i];
            
            if (order.empty() || order.back() < sequence[i]) {
                order.push_back(sequence[i]);
                record[i] = order.size() - 1;
            } else {
                find_lower_bound(i);
            }
        }
    }

    void find_lower_bound(int idx) {
        int low = 0;
        int high = order.size() - 1;
        
        while(low < high) {
            int mid = (low + high) / 2;
            
            if (order[mid] < sequence[idx]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }

        order[low] = sequence[idx];
        record[idx] = low;
    }

    LIS(int sz) {
        size = sz;
        sequence = vector<int>(sz);
        record = vector<int>(sz);
    }
};

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int N, num;
    cin >> N;

    LIS longest_increase_sequence = LIS(N);
    longest_increase_sequence.get_input();
    
    cout << longest_increase_sequence.order_size() << "\n";
    int cnt = longest_increase_sequence.order_length();
    int sp = longest_increase_sequence.record_length();

    for (int i = sp ; i >= 0 ; i--) {
        if(cnt == -1) break;
        if(longest_increase_sequence.is_eqaul_record(cnt, i)) {
            cnt = longest_increase_sequence.change_order_from_seq(cnt, i);
        }
    }

    for(int it : longest_increase_sequence.get_order()) {
        cout << it << " ";
    }
}

---

느낀점: 심심해서 클래스를 통해서 구현해보았는데 main만 봤을 때 조금 더 이해하기 편한 것 같다.

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

14003번: 가장 긴 증가하는 부분 수열 5