백준 14002 - 가장 긴 증가하는 부분 수열 4

문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 주어진 배열에서 가장 긴 증가하는 부분 수열을 뽑는다.

그 길이와 요소를 출력해야 한다.

 

우선, 가장 긴 증가하는 부분 수열을 뽑는 과정은 다음과 같다.

배열을 하나씩 탐색하며 해당 요소 이전에 나온 자신보다 작은 요소 중 가장 긴 부분 수열을 뽑은 뒤 자신을 추가하면 가장 긴 증가하는 부분 수열이 된다.

예를 들어 보자.

30을 탐색하는 과정에서 20은 [10, 20]으로 가장 긴 증가하는 부분 수열이다.

이는 메모이제이션을 통해 기록해 놓을 것이므로 해당 부분의 길이를 $O(1)$에 알 수 있다.

즉, 위의 경우를 메모이제이션 상태는 다음과 같다.

 

그렇다면 이를 어떻게 기록할 것인가는 간단하다.

자신 이전의 요소 중 자신보다 작은 부분의 길이 중 가장 긴 요소에 1을 더하면 된다.

for (int k = 0; k < N; k++)
{
   length[k] = 1;
   select[k] = k;
   for (int i = 0; i < k; i++)
   {
       if (nums[i] < nums[k])
       {
           if (length[k] < length[i] + 1)
           {
               length[k] = length[i] + 1;
               select[k] = i;
           }
       }
   }

   if (length[cursor] < length[k]) cursor = k;
}

length는 부분 수열의 길이를 저장하는 배열이다.

select는 선택한 요소를 가져오기 위한 테크닉이다.

해당 요소가 이전의 어떤 요소를 선택했는지 알고 있다면 계속하여 추적할 수 있다.

또한, cursor는 가장 긴 부분 수열을 갖고 있는 요소의 인덱스이다.

cursor을 최초로하여 요소들을 역추적하는 방법은 다음과 같다.

vector<int> selectedNum;
selectedNum.push_back(cursor);
cout << length[cursor] << "\n";

while (cursor != select[cursor])
{
    selectedNum.push_back(select[cursor]);
    cursor = select[cursor];
}

for (int i = selectedNum.size() - 1; i >= 0; i--)
{
    cout << nums[selectedNum[i]] << " ";
}

부분 수열의 처음부터 출력해야 하기 때문에 vector를 이용하여 한 번 더 저장하는 과정을 거쳤다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

int N;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    vector<int> nums(N);
    vector<int> length(N, 0);
    vector<int> select(N, 0);
    for (int i = 0; i < N; i++)
    {
        cin >> nums[i];
    }

    int cursor = 0;

    for (int k = 0; k < N; k++)
    {
        length[k] = 1;
        select[k] = k;
        for (int i = 0; i < k; i++)
        {
            if (nums[i] < nums[k])
            {
                if (length[k] < length[i] + 1)
                {
                    length[k] = length[i] + 1;
                    select[k] = i;
                }
            }
        }

        if (length[cursor] < length[k]) cursor = k;
    }

    vector<int> selectedNum;
    selectedNum.push_back(cursor);
    cout << length[cursor] << "\n";

    while (cursor != select[cursor])
    {
        selectedNum.push_back(select[cursor]);
        cursor = select[cursor];
    }

    for (int i = selectedNum.size() - 1; i >= 0; i--)
    {
        cout << nums[selectedNum[i]] << " ";
    }

    return 0;
}

---