[백준] 최대 증가 부분 수열(LIS) 문제

가장 긴 증가하는 부분 수열 (실 2) : https://www.acmicpc.net/problem/11053
가장 긴 증가하는 부분 수열 4 (골 4) :https://www.acmicpc.net/problem/14002

DP에 관하여 워낙 유명한 문제.

여기서는 LIS를 실제로 출력하는 코드를 위주로 살펴본다.

---

1. (일반적인) 최대 증가 부분 수열의 길이 반환

 

#include <iostream>
#include <stdio.h>
#include <memory.h>

using namespace std;

int N, A[1001], cache[1001];

int lis(int start)
{
  int &ret = cache[start + 1];

  if (ret != -1)
    return ret;

  ret = 1;

  for (int i = start + 1; N > i; i++)
    if (start == -1 || A[start] < A[i])
      ret = max(ret, lis(i) + 1);

  return ret;
}

int main(void)
{
  int k;

  cin >> N;

  for (int i = 0; N > i; i++)
  {
    scanf("%d", &k);
    A[i] = k;
  }

  memset(cache, -1, sizeof(cache));

  int maxLen = 0;

  maxLen = lis(-1);

  cout << maxLen - 1<< '\n';

  return 0;
}

 

---

 

2. LIS 실제 출력 문제

실제 답 계산 레시피(https://sanghoonly.tistory.com/44)를 참고.

#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <vector>

using namespace std;

int N, A[1001], cache[1001];
int choices[1001];  // 어느 숫자를 다음 숫자로 선택해야, LIS의 길이를 최대화 할 수 있을지를 기록하는 배열.
vector<int> result; // lis 실제 결과를 담는 벡터.

int lis(int start)
{
  int &ret = cache[start + 1];

  if (ret != -1)
    return ret;

  ret = 1;

  int bestNext = -1; // LIS 길이를 최대화할 선택의 idx.

  for (int i = start + 1; N > i; i++)
    if (A[start] < A[i])
    {
      int cand = lis(i) + 1;
      if (cand > ret)
      {
        bestNext = i;
        ret = cand;
      }
    }

  choices[start + 1] = bestNext; //최적 선택을 choices에다 저장.

  return ret;
}

// choice값을 이용하여, LIS를 재구성하는 재귀 함수.
void reconstruct(int start, vector<int> &seq)
{
  if (start != -1)
    seq.push_back(A[start]); // 선택 값을 벡터에다 저장.

  // lis 함수에서 choices[start + 1]에 최적 선택의 인덱스를 담았으므로, 이를 복원.
  int next = choices[start + 1]; 

  if (next != -1)
    reconstruct(next, seq);
}

int main(void)
{
  int k;

  cin >> N;

  for (int i = 0; N > i; i++)
  {
    scanf("%d", &k);
    A[i] = k;
  }

  memset(cache, -1, sizeof(cache));
  memset(choices, -1, sizeof(choices));

  int maxLen = 0;

  maxLen = lis(-1) - 1;

  cout << maxLen << '\n';

  reconstruct(-1, result);

  for (auto e : result)
  {
    cout << e << ' ';
  }
  return 0;
}