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

문제 링크

7570번 - 줄 세우기

설명

아이들을 번호 순서대로 줄 세우기 위해 맨 앞이나 맨 뒤로 보내는 최소 횟수를 구하는 문제입니다.

접근법

핵심은 이미 올바른 순서로 연속되어 있는 아이들은 움직일 필요가 없다는 점입니다. 예를 들어 1, 2, 3번이 순서대로 서 있다면 이들은 그대로 두고 나머지만 옮기면 됩니다.

입력을 순서대로 읽으면서 각 번호가 바로 앞 번호에 이어서 나타나는지 확인합니다. 어떤 번호까지 연속으로 이어지는 길이를 기록하고, 그 중 가장 긴 길이를 찾습니다.

전체 인원에서 이 최장 연속 길이를 빼면 움직여야 하는 아이들의 수가 됩니다.

---

Code

C#

using System;
using System.IO;

class FastScanner {
  private readonly byte[] buf = new byte[1 << 16];
  private int idx, len;
  private int ReadByte() {
    if (idx >= len) {
      len = Console.OpenStandardInput().Read(buf, 0, buf.Length);
      idx = 0;
      if (len == 0) return -1;
    }
    return buf[idx++];
  }
  public int NextInt() {
    int c, sign = 1, val = 0;
    do c = ReadByte(); while (c <= ' ');
    if (c == '-') { sign = -1; c = ReadByte(); }
    while (c > ' ') { val = val * 10 + (c - '0'); c = ReadByte(); }
    return val * sign;
  }
}

class Program {
  static void Main() {
    var fs = new FastScanner();
    var n = fs.NextInt();
    var cache = new int[n + 2];
    var maxLen = 0;

    for (var i = 0; i < n; i++) {
      var num = fs.NextInt();
      cache[num] = cache[num - 1] + 1;
      if (cache[num] > maxLen) maxLen = cache[num];
    }

    Console.WriteLine(n - maxLen);
  }
}

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 dp(n + 2, 0);
  int best = 0;
  for (int i = 0; i < n; i++) {
    int x; cin >> x;
    dp[x] = dp[x - 1] + 1;
    if (dp[x] > best) best = dp[x];
  }
  cout << n - best << "\n";

  return 0;
}