[백준 2631] 줄세우기 (C#, C++) - soo:bak

문제 링크

2631번 - 줄세우기

설명

1부터 N까지 번호가 적힌 아이들이 뒤섞여 서 있을 때, 번호 순서대로 다시 세우기 위해 옮겨야 하는 최소 인원을 구하는 문제입니다.

접근법

이미 올바른 순서로 서 있는 아이들은 그대로 두고, 나머지만 옮기면 됩니다.

예를 들어 3, 7, 5, 2, 6, 1, 4 순서에서 3, 5, 6은 서로 순서가 맞으므로 그대로 둘 수 있습니다.

이렇게 순서가 맞는 아이들 중 가장 많은 경우를 찾으면, 그것이 가장 긴 증가하는 부분 수열입니다.

전체 인원에서 이 길이를 빼면 옮겨야 하는 최소 인원이 됩니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var a = new int[n];
    for (var i = 0; i < n; i++) a[i] = int.Parse(Console.ReadLine()!);

    var dp = new int[n];
    var lis = 0;
    for (var i = 0; i < n; i++) {
      dp[i] = 1;
      for (var j = 0; j < i; j++) {
        if (a[j] < a[i] && dp[i] < dp[j] + 1)
          dp[i] = dp[j] + 1;
      }
      if (lis < dp[i]) lis = dp[i];
    }

    Console.WriteLine(n - lis);
  }
}

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 a(n), dp(n, 1);
  for (int i = 0; i < n; i++) cin >> a[i];

  int lis = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
      if (a[j] < a[i] && dp[i] < dp[j] + 1)
        dp[i] = dp[j] + 1;
    }
    if (lis < dp[i]) lis = dp[i];
  }

  cout << (n - lis) << "\n";

  return 0;
}