[伯俊][2631]キュー-JavaScript

問題の説明

KOI幼稚園にはN人の子供がいます.今日は遠足の日です.先生は1番からN番までの番号を子供たちの胸に貼った.子供たちを効果的に保護するために、先生は彼らに番号順に並んで目的地まで行かせた.移動途中で見ると、子供達の番号順が変わっていました.だから先生は子供たちの位置を移して、番号順に並び直したいと思っています.また、子供たちが混乱しないように、移動位置の子供の数をできるだけ減らす.
たとえば、7人の子供が次の順序で並んでいるとします.
3 7 5 2 6 1 4
子供たちが順番に並ぶように、まず4番の子供を7番の子供の後ろに移動します.これで以下の手順になります.
3 7 4 5 2 6 1
今、7番の子供を最後に移します.
3 4 5 2 6 1 7
次の1番の子供を一番前に移動します.
1 3 4 5 2 6 7
最後に2番の子を1番の子の後ろに移し、番号順に並べます.
1 2 3 4 5 6 7
上記の方法で,合計4人の子供を移し,番号順に並んだ.上の例では、3人の子供だけが運べず、順番に仕事をすることができません.そのため、4人を移すのは最も少ない子供です.N명의 아이들이 임의의 순서로 줄을 서 있을 때, 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 프로그램을 작성に電話してください.

入力

1列目は子供にNを数える.2行目から、1からNの数字が1行1つです.N은 2 이상 200 이하의 정수.

しゅつりょく

1行目は番号順に並び、移された子供の最小数を出力します.

［入力例1］

7
3
7
5
2
6
1
4

［例出力1］

4

に答える

上記の例を例として1と入力すると、最初の例は以下のようになります.

この問題では、子供をどこにでも置くことができるので、전체 중에서 가장 길게 부분적으로나 연속적으로 큰 번호를 가진 아이들을 기준으로 삼으면 된다.のように、残りの人を移すだけで最低限の移動に必要な結果を得ることができます.

すべての子供の中で最も長い部分や連続する大きな番号を基準にします。

基準を定めるためにLISアルゴリズムを用いることができる.
上記の例では、LISを用いて3、5、6の長さの3を得ることができる.そうなると、残りの4人を移すだけで、最低限の移動で昇順に並べることができます.

// N은 아이들의 수
// data = [3, 7, 5, 2, 6, 1, 4] 아이들의 번호
for (let i = 1; i < N; i++) {
  dp[i] = 1;
  for (let j = 0; j < i; j++) {
    if (data[i] > data[j] && dp[i] < dp[j] + 1) {
      dp[i] = dp[j] + 1;
    }
  }
  if (maxLength < dp[i]) maxLength = dp[i];
}

上記のコードで使用されるdp配列に格納される値は각 인덱스에서의 부분적으로나 연속적으로 큰 번호를 가진 아이들의 인원 수である.data = [3, 7, 5, 2, 6, 1, 4] 아이들의 번호たとえば、i = 2の場合(5番子供)、dp[2]が持つ値は2명(3番子供、5番子供)です.

if条件文で使用される2つの条件

1. data[i] > data[j]LISアルゴリズムは増加した値を設定する必要があるので,i値とi以前の値jを比較することによって小さいかどうかの条件を決定する.
2. dp[i] < dp[j] + 11番の条件だけを確認すると、希望の結果が得られません.data = [3, 7, 5, 2, 6, 1, 4] 아이들의 번호例えば、i = 4の場合(6番子供)、dp[4]が持つ値は4명(3番子供、5番子供、2番子供、6番子供)です.2번 아이는 부분적으로나 연속적으로 큰 번호가 아니다.上記を排除するため、dp[i] < dp[j] + 1条件を追加しました.dp배열이 가지는 값의 의미를 다시 생각해보며 dp[i=4] < dp[j=3] + 1なら、dp[3] = 1명(2番子供)の値があるはずですが、dp[4] = 현재 3명(3番子供、5番子供、6番子供)があるので、dp[3]の場合、6番子供を追加したときの値と現在のdp[4]の値を比較して、追加した値が大きくなったときに子供を追加すればよいのです.

基準を決めてから。

基準が定められていれば、全体の人数から基準人数(전체 인원수 - dp배열 중 가장 큰 값)を差し引くと結果値が得られます.

最終コード

const solution = (N, data) => {
    const dp = new Array(N).fill(0);
    let maxLength = 0;

    for (let i = 0; i < N; i++) {
        dp[i] = 1; // 자신은 포함되어 있어야 하기 때문에 
        for (let j = 0; j < i; j++) {
            if (data[i] > data[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
        if (maxLength < dp[i]) maxLength = dp[i];
    }

    // answer
    console.log(N - maxLength);
};

const fs = require('fs');

const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const N = +input[0];
const data = [];
for (let i = 1; i <= N; i++) {
    data.push(+input[i]);
}

solution(N, data);