가장 긴 증가하는 부분 수열4, 5

jaimemin.tistory.com/1095 를 참고하여 해결하였습니다.

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

처음에는 가장 긴 증가하는 부분 수열 1, 2, 3에서 해결한 방법과 똑같이 접근을 했고 lower_bound로 만든 배열의 값을 출력해서 제출했었습니다.

그 결과 '틀렸습니다'를 받았고 반례가 생각나지 않아 위 블로그를 참고해서 해결하였습니다.

vector<int> lis 는 어떤 값을 저장하는가?

가장 긴 증가하는 부분 수열 1, 2, 3과 마찬가지로 가장 길게 증가하는 크기를 구하기 위해 사용하는 배열

 

vector<pair<int, int>> answer는 어떤 값을 저장하는가?

answer[i]은 {0 ~ i번째 중 몇 번째로 증가하는 수열인가, 입력받은 값인 input[i]}를 저장

 

answer배열을 왜 써야 하는가?

단순히 크기를 구하는 문제를 해결할 때에는 answer배열을 사용하지 않고 lis배열의 크기만 출력해주면 된다.

그렇지만 이 문제는 가장 길게 증가하는 배열의 크기와 그때의 원소들을 모두 출력해줘야 하는데 그냥 lis값을 출력했을 때의 반례는 다음과 같다.

8

1 5 3 4 2 6 7 8
올바른 정답은 1 3 4 6 7 8이지만 lis값은 1 2 4 6 7 8값이 나오게 된다.

따라서 몇 번째로 증가하는지에 대한 정보를 이용해서 input배열의 끝(i 가 N - 1일 때)에서부터 수열을 찾아준다. 

 

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#define MAX 1000001
using namespace std;
vector<int> input(MAX), lis;
vector<pair<int, int>> answer(MAX);

int main(void) {
    int N;
    cin >> N;
    for(int i = 0; i < N; i++) cin >> input[i];

    lis.push_back(input[0]);
    answer[0] = {1, input[0]};

    for(int i = 1; i < N; i++) {
        vector<int>::iterator idx2 = lower_bound(lis.begin(), lis.end(), input[i]);
        if(idx2 == lis.end()) { //lis에 있는 값 중에 가장 큰 값이라면
            lis.push_back(input[i]);
            answer[i] = {lis.size(), input[i]};
        } else {
            lis[idx2 - lis.begin()] = input[i];
            answer[i] = {idx2 - lis.begin() + 1, input[i]};
        }
    }

    stack<int> s;
    int idx = lis.size();
    cout << lis.size() << endl;
    for(int i = N - 1; i >= 0; i--) {
        if(answer[i].first == idx) {
            s.push(answer[i].second);
            idx--;
        }
    }

    while(!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }

    return 0;
}

 

www.acmicpc.net/problem/14002

14002번: 가장 긴 증가하는 부분 수열 4

www.acmicpc.net/problem/14003

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