백준 14003 - 가장 긴 증가하는 부분 수열 5(C++)

문제 링크 입니다 https://www.acmicpc.net/problem/14003

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

https://junseok.tistory.com/23 이 문제의 심화 문제 입니다.

백준 12015 - 가장 긴 증가하는 부분 수열2(복습)

 

lower_bound를 사용하여 증가하는 부분 수열을 구할 때 수열의 길이는 정확하게 구해지지만, 수열은 정확하게 구해지지 않습니다. 이때 어떤 방식을 사용해야지 수열의 내용까지 정확하게 구할 수 있냐를 물어보는 문제입니다.

ex) 수열이 10, 20, 40, 45, 70, 30이라고 할 때 lower_bound를 사용한다면 

(10) -> (10, 20) -> (10, 20, 40) -> (10, 20, 40, 45) ->  (10, 20, 40, 45, 70) -> (10, 20, 30, 45, 70) 

따라서 수열의 길이는 5이지만, 수열은 맞지 않는 현상이 생깁니다. 

 

위와 같은 문제를 해결하여 정확한 수열을 구하기 위해서는 수의 위치를 기억하는 배열이 하나 필요합니다.

위와 같은 수열일 때, 30은 40보다 작지만, 위치는 뒤에 있기에 수를 바꾸지 않는 것입니다.

 

저는 수열의 해당 위치에 수열이 몇번 째로 저장되는지를 알 수 있는 배열 하나를 만들어서 사용했습니다.

ex) 10, 20, 40, 45, 70, 30, 15의 수열이 있다고 했을때,

1. 10(1) 저장

2. 10(1), 20(2) 저장

3. 10(1), 20(2), 40(3) 저장

4. 10(1), 20(2), 40(3), 45(4) 저장

5. 10(1), 20(2), 40(3), 45(4) 저장

6. 10(1), 20(2), 40(3), 45(4), 70(5) 저장

7. 10(1), 20(2), 30(3), 45(4), 70(5) 저장 / 40(3)

8. 10(1), 15(7), 30(6), 45(4), 70(5) 저장 / 40(3), 20(2)

이 실행이 끝나고 나면, 순서를 저장하는 배열에는 (1, 2, 3, 4, 5, 3, 2)가 저장이 됩니다. 

이때 가장 긴 수열의 길이는 5임으로 배열 뒤에서 순서대로 5, 4, 3, 2, 1를 찾은 뒤에 출력을 하는 것입니다!

 

 

이분 탐색을 활용한 수열 찾기는 위의 블로그를 참고해주세요!

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cstring>
#include <string.h>
#include <cmath>
using namespace std;

int N;
int arr[1000001];
int order[1000001];
vector<int> maxi;
vector<int> ans; 

void solve() {
    for (int i = 1; i < N; i++) {
        if (maxi.back() < arr[i]) {
            maxi.push_back(arr[i]);
            order[i] = maxi.size();
        }
        else {
            int low = 0;
            int high = maxi.size()-1;
            int ret = 100000001;
            while (low <= high) {
                int mid = (low + high) / 2;
                if (maxi[mid] >= arr[i]) {
                    if (ret > mid) ret = mid;
                    high = mid - 1;
                }
                else low = mid + 1;
            }
            maxi[ret] = arr[i];
            order[i] = ret + 1;
        }
    }
    cout << maxi.size() << "\n";
    int Find = maxi.size();
    for (int i = N - 1; i >= 0; i--) {
        if (Find == 0) break;
        if (order[i] == Find) {
            Find--;
            ans.push_back(arr[i]);
        }
    }
    for (int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i] << " ";
    }
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    maxi.push_back(arr[0]);
    order[0] = 1;
    solve();
    return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!