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

6
10 20 10 30 20 50

4
10 20 30 50

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

#include <iostream>
#include <vector>

using namespace std;

int n; // 수열의 개수
vector<vector<int>> Sequences;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    if (n <= 0) return 0;

    int num;
    cin >> num;

    // 첫 번째 수로 초기 시퀀스 하나 생성
    vector<int> sequence;
    sequence.push_back(num);
    Sequences.push_back(sequence);

    for (int i = 1; i < n; i++)
    {
        cin >> num;
        int length = Sequences.size();

        bool canExtend = false;
        vector<vector<int>> newSequences;

        // 기존 시퀀스들을 모두 검사
        for (int j = 0; j < length; j++)
        {
            int last = Sequences[j].back();

            // 확장 가능한 경우 : 새로운 시퀀스 생성
            if (last < num)
            {
                canExtend = true;
                vector<int> extendedSeq = Sequences[j];
                extendedSeq.push_back(num);
                newSequences.push_back(extendedSeq);
            }
        }

        // 어떤 시퀀스에도 붙지 못하면 새로운 시퀀스 시작
        if (!canExtend)
        {
            vector<int> newSeq;
            newSeq.push_back(num);
            newSequences.push_back(newSeq);
        }

        // 새로 생긴 시퀀스들을 기존에 합침
        for (auto& seq : newSequences)
            Sequences.push_back(seq);

        // 최적 시퀀스 길이 및 꼬리값 계산
        int maxSeqSize = 0;
        int bestIndex = 0;
        int bestTail = 1000000001;

        for (int j = 0; j < (int)Sequences.size(); j++)
        {
            int sz = Sequences[j].size();
            int tail = Sequences[j].back();
            if (sz > maxSeqSize || (sz == maxSeqSize && tail < bestTail))
            {
                maxSeqSize = sz;
                bestTail = tail;
                bestIndex = j;
            }
        }

        // 가지치기: 같은 길이인데 꼬리값이 큰 시퀀스 제거
        for (int j = 0; j < (int)Sequences.size();)
        {
            int sz = Sequences[j].size();
            int tail = Sequences[j].back();

            if (sz == maxSeqSize && tail > bestTail)
            {
                Sequences.erase(Sequences.begin() + j);
            }
            else
            {
                j++;
            }
        }
    }

	// 결과 중 가장 긴 시퀀스 찾기
    int maxSize = 0;
    int bestIdx = 0;
    for (int i = 0; i < (int)Sequences.size(); i++)
    {
        if (Sequences[i].size() > maxSize)
        {
            maxSize = Sequences[i].size();
            bestIdx = i;
        }
    }

    cout << maxSize << "\n";
    for (int x : Sequences[bestIdx])
        cout << x << " ";

    return 0;
}

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// (LIS, Longest Increasing Subsequence)

int main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int N;
    std::cin >> N;

    vector<int> input(N);
    for (int i = 0; i < N; i++)
        std::cin >> input[i];

    vector<int> tail;  // LIS를 구성하는 인덱스들
    vector<int> prev_idx(N, -1);  //각 요소가 LIS에 포함될 때, 그 직전 요소의 인덱스를 저장


    for (int i = 0; i < N; i++)
    {
        // 이분 탐색으로 input[i]가 tail 배열에서 들어가야 할 위치 찾기
        int lo = 0;
        int hi = (int)tail.size() - 1;
        int pos = (int)tail.size(); // 기본값은 맨 뒤

        while (lo <= hi)
        {
            int mid = (lo + hi) / 2;
            // input[i]보다 크거나 같은 첫 번째 tail 원소 위치(pos)를 찾
            if (input[tail[mid]] < input[i])
            {
                lo = mid + 1;
            }
            else
            {
                pos = mid;
                hi = mid - 1;
            }
        }

        // 이전 인덱스 설정
        if (pos > 0)
        {
            prev_idx[i] = tail[pos - 1];
        }
        else
        {
            prev_idx[i] = -1;  // 첫 번째 요소
        }

        // tail 업데이트
        if (pos == (int)tail.size())
        {
            tail.push_back(i);
        }
        else
        {
            tail[pos] = i;
        }
    }

    // 결과: LIS 길이
    int lis_len = (int)tail.size();
    std::cout << lis_len << "\n";

    // 실제 LIS 수열 재구성
    vector<int> lis;
    for (int idx = tail.back(); idx != -1; idx = prev_idx[idx])
    {
        lis.push_back(input[idx]);
    }
    reverse(lis.begin(), lis.end());

    for (int v : lis)
        std::cout << v << " ";
    std::cout << "\n";

    return 0;
}

input = [5, 2, 8, 6, 3, 6, 9, 7]

이분 탐색을 이용한 LIS 구성 로직

input = [3, 5, 2, 7, 4, 1, 8]

--------------------------------

i=0 (값: 3)
tail: [] (빈 배열)
이분탐색: tail.size() = 0 → while문 스킵
pos = 0 (기본값)

prev_idx[0] = -1 (pos=0이므로)
tail 업데이트: pos == tail.size() → push_back(0)
결과: tail = [0] (값: [3])

--------------------------------

i=1 (값: 5)
tail: [0] (값: [3])
이분탐색:
  lo=0, hi=0, mid=0
  input[tail[0]] = 3 < 5 → lo = mid+1 = 1
  lo=1 > hi=0 → 종료
pos = tail.size() = 1

prev_idx[1] = tail[0] = 0 (5 앞에 3)
tail 업데이트: push_back(1)
결과: tail = [0,1] (값: [3,5])

--------------------------------

i=2 (값: 2)
tail: [0,1] (값: [3,5])
이분탐색:
  lo=0, hi=1, mid=0
  input[tail[0]] = 3 >= 2 → pos=0, hi=-1
  lo=0 > hi=-1 → 종료
pos = 0

prev_idx[2] = -1 (pos=0이므로)
tail 업데이트: tail[0] = 2
결과: tail = [2,1] (값: [2,5])

--------------------------------

i=3 (값: 7)
tail: [2,1] (값: [2,5])
이분탐색:
  lo=0, hi=1, mid=0: input[tail[0]]=2 < 7 → lo=1
  lo=1, hi=1, mid=1: input[tail[1]]=5 < 7 → lo=2
  lo=2 > hi=1 → 종료
pos = tail.size() = 2

prev_idx[3] = tail[1] = 1 (7 앞에 5)
tail 업데이트: push_back(3)
결과: tail = [2,1,3] (값: [2,5,7])

--------------------------------

i=4 (값: 4)
tail: [2,1,3] (값: [2,5,7])
이분탐색:
  lo=0, hi=2, mid=1: input[tail[1]]=5 >= 4 → pos=1, hi=0
  lo=0, hi=0, mid=0: input[tail[0]]=2 < 4 → lo=1
  lo=1 > hi=0 → 종료
pos = 1

prev_idx[4] = tail[0] = 2 (4 앞에 2)
tail 업데이트: tail[1] = 4
결과: tail = [2,4,3] (값: [2,4,7])

--------------------------------

i=5 (값: 1)
tail: [2,4,3] (값: [2,4,7])
이분탐색:
  lo=0, hi=2, mid=1: input[tail[1]]=4 >= 1 → pos=1, hi=0
  lo=0, hi=0, mid=0: input[tail[0]]=2 >= 1 → pos=0, hi=-1
  lo=0 > hi=-1 → 종료
pos = 0

prev_idx[5] = -1
tail 업데이트: tail[0] = 5
결과: tail = [5,4,3] (값: [1,4,7])

--------------------------------

i=6 (값: 8)

tail: [5,4,3] (값: [1,4,7])
이분탐색:
  lo=0, hi=2, mid=1: input[tail[1]]=4 < 8 → lo=2
  lo=2, hi=2, mid=2: input[tail[2]]=7 < 8 → lo=3
  lo=3 > hi=2 → 종료
pos = tail.size() = 3

prev_idx[6] = tail[2] = 3 (8 앞에 7)
tail 업데이트: push_back(6)
결과: tail = [5,4,3,6] (값: [1,4,7,8])