[백준 2550] 전구 (C#, C++) - soo:bak

문제 링크

2550번 - 전구

설명

스위치와 전구가 같은 번호끼리 연결될 때, 선이 교차하지 않도록 켤 수 있는 전구의 최대 개수와 해당 스위치 번호들을 구하는 문제입니다.

스위치 순서가 고정되어 있으므로, 각 스위치가 연결되는 전구의 위치를 배열로 만들면 전깃줄 문제와 동일해집니다. 이 배열의 가장 긴 증가하는 부분 수열(LIS)이 교차 없이 켤 수 있는 최대 전구 집합이 됩니다.

접근법

먼저 각 전구 번호가 몇 번째 위치에 있는지 기록합니다.

다음으로 스위치 순서대로 연결된 전구의 위치를 배열로 만듭니다. 이 배열에서 LIS를 구하면서 경로를 역추적할 수 있도록 이전 인덱스를 함께 저장합니다.

이후 LIS에 포함된 스위치 번호들을 역추적하여 오름차순으로 출력합니다.

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

---

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var switches = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      var lamps = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);

      var posLamp = new int[10001];
      for (var i = 0; i < n; i++)
        posLamp[lamps[i]] = i;

      var seq = new int[n];
      for (var i = 0; i < n; i++)
        seq[i] = posLamp[switches[i]];

      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 = seq[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++;
      }

      Console.WriteLine(len);

      var keep = new List<int>();
      for (var cur = lisPos[len - 1]; cur != -1; cur = prev[cur])
        keep.Add(switches[cur]);
      keep.Sort();

      Console.WriteLine(string.Join(" ", keep));
    }
  }
}

C++

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

typedef vector<int> vi;

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

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

  vi posLamp(10001, -1);
  for (int i = 0; i < n; i++)
    posLamp[lamp[i]] = i;

  vi seq(n);
  for (int i = 0; i < n; i++)
    seq[i] = posLamp[sw[i]];

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

  for (int i = 0; i < n; i++) {
    int x = seq[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";

  vi keep;
  for (int cur = lisPos[len - 1]; cur != -1; cur = prev[cur])
    keep.push_back(sw[cur]);
  sort(keep.begin(), keep.end());
  for (size_t i = 0; i < keep.size(); i++) {
    cout << keep[i];
    if (i + 1 < keep.size())
      cout << ' ';
  }
  cout << "\n";

  return 0;
}