[백준 14003] 가장 긴 증가하는 부분 수열 5 (C#, C++) - soo:bak

문제 링크

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

설명

길이 N (1 ≤ N ≤ 1,000,000)의 정수 수열이 주어지는 상황에서, 가장 긴 증가하는 부분 수열의 길이와 그 수열을 구하는 문제입니다.

이 문제는 14002번 - 가장 긴 증가하는 부분 수열 4과 동일한 문제이지만, N이 최대 백만까지 가능하고 값의 범위가 -10억부터 10억까지입니다.

알고리듬 자체는 14002번과 동일하지만, N이 1000배 크므로 빠른 I/O가 필수적입니다.

접근법

이진 탐색 기반 LIS 알고리즘에 경로 복원 기능을 추가합니다.

먼저 세 개의 배열을 사용합니다. lisVal[len]은 길이 len인 LIS의 마지막 값을, lisPos[len]은 그 값의 원본 인덱스를, prev[i]는 인덱스 i를 마지막으로 하는 LIS의 이전 원소 인덱스를 저장합니다.

다음으로 각 원소를 순회하며 lower_bound로 lisVal 배열에서 현재 원소가 들어갈 위치를 찾습니다. 이 위치가 현재 원소의 LIS 길이가 됩니다.

이후 prev[i]를 이전 위치의 인덱스로 설정하고, lisVal과 lisPos를 갱신합니다. LIS 길이가 늘어났다면 전체 길이도 증가시킵니다.

마지막으로 최종 LIS의 마지막 인덱스에서 시작하여 prev 배열을 따라가며 역순으로 수열을 복원합니다.

시간 복잡도는 O(N log N)입니다.

---

Code

C#

using System;
using System.Collections.Generic;
using System.IO;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      using var sr = new StreamReader(Console.OpenStandardInput());
      using var sw = new StreamWriter(Console.OpenStandardOutput());

      var n = int.Parse(sr.ReadLine()!);
      var arr = Array.ConvertAll(sr.ReadLine()!.Split(), int.Parse);

      var lisVal = new int[n];
      var lisPos = new int[n];
      var prev = new int[n];
      var len = 0;

      for (var i = 0; i < n; i++) {
        var x = arr[i];
        var idx = Array.BinarySearch(lisVal, 0, len, x);
        if (idx < 0)
          idx = ~idx;

        prev[i] = (idx == 0) ? -1 : lisPos[idx - 1];
        lisVal[idx] = x;
        lisPos[idx] = i;
        if (idx == len)
          len++;
      }

      sw.WriteLine(len);

      var result = new List<int>();
      for (var cur = lisPos[len - 1]; cur != -1; cur = prev[cur])
        result.Add(arr[cur]);
      result.Reverse();

      sw.WriteLine(string.Join(" ", result));
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef stack<int> si;

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

  int n; cin >> n;
  vi a(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];

  vi lisVal(n), lisPos(n), prev(n);
  int len = 0;

  for (int i = 0; i < n; i++) {
    int x = a[i];
    auto it = lower_bound(lisVal.begin(), lisVal.begin() + len, x);
    int idx = it - lisVal.begin();

    prev[i] = (idx == 0) ? -1 : lisPos[idx - 1];
    lisVal[idx] = x;
    lisPos[idx] = i;
    if (idx == len)
      len++;
  }

  cout << len << "\n";
  si st;
  for (int cur = lisPos[len - 1]; cur != -1; cur = prev[cur])
    st.push(a[cur]);
  while (!st.empty()) {
    cout << st.top(); st.pop();
    if (!st.empty())
      cout << ' ';
  }
  cout << "\n";

  return 0;
}