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

작성일 | In |

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

유형 : LIS, Backtracking

문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에
가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

예제 입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

1
2
6
10 20 10 30 20 50

예제 출력

출력 설명

1
2
4
10 20 30 50

해결 전략

이분탐색을 이용하여 LIS 길이를 찾는다.
부분 수열을 백트래킹 해서 찾는다.
LIS를 만들때, path에 {숫자, 숫자가 등장한 idx} 를 보관해서 풀어야 한다.
LIS 길이를 구한 후, path에 담긴 원소들을 뒤에서부터 차례대로 탐색해야 정상적인 경로를 뽑을 수 있다.

주의할 점

  • 삽입시 자신의 앞 경로를 LIS를 만들기 위한 벡터내의 앞 숫자로 잡으면 틀린다.
  • 맞왜틀 하고 있다면 아래의 반례를 넣어보기 바란다.
1
2
6
1 3 5 7 2 3

풀이

LIS를 이분탐색을 이용하여 구한다.

  • LIS를 만들기 위해 초기 원소는 나올 수 없는 최소의 수로 한다. INT_MIN
  • 맨 뒤보다 들어가려는 숫자 num 이 더 크다면, 뒤에 넣는다.
  • 그렇지 않다면, 최적의 위치를 lower_bound를 이용해 찾아서 넣는다.
  • 두가지 경우 모두 LIS를 위한 벡터에 삽입할 때마다
    • path에 해당 num이 LIS를 구성할때 어느 위치에 있는지를 찾아 같이 넣어준다.

경로를 찾는다.

  • path의 맨 뒤에서부터 탐색한다.
  • 만약 path안의 원소의 위치 index가, LIS를 이루는 수열 index와 같다면
    • 해당 숫자는 LIS를 이루는 구성 요소가 된다.
      • 스택에 넣는다.
  • 스택안에 들어간것을 역순으로 출력한다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
#define pp pair<int, int>
#define index first
#define value second

using namespace std;

int n;

vector<int> vec{ INT_MIN };
vector<pp> path;
stack<int> s;

void print_path() {
    int idx = vec.size() - 1;

    for (int i = path.size() - 1; i >= 0; --i) {
        if (path[i].index != idx)continue;
        s.push(path[i].value);
        idx--;
    }

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

void make_sequence(int num) {
    int idx;
    if (num > vec.back()) {
        idx = vec.size();
        vec.push_back(num);
    }
    else {
        auto it = lower_bound(vec.begin(), vec.end(), num);
        idx = it - vec.begin();
        *it = num;
    }
    path.push_back({idx, num });
}
void solve() {
    int num;
    for (int i = 0; i < n; ++i) {
        cin >> num;
        make_sequence(num);
    }
    cout << vec.size() - 1 << "\n";
    print_path();
}

void input() {
    cin >> n;
}
int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    cin.tie(NULL);  cout.tie(NULL);
    input();
    solve();

    return 0;
}

피드백

뭔가 글로 설명하려니 굉장히 힘드네요
나의 경우에도 주의할점 을 놓치고 있어서 맞왜틀 하고 있었다.