99클럽 코테 스터디 31일차 TIL

미들러

문제

2631번: 줄세우기

#동적계획법

https://www.acmicpc.net/problem/2631

풀이

n명의 아이들의 번호가 주어졌을 때 번호순으로 아이들을 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 문제이다.

옮겨지는 아이들의 수를 최소로 하려면 그대로 있는 아이들의 수를 최대로 하면 된다.

즉 이미 오름차순으로 서있는 아이들의 수의 최댓값을 구한 후 n에서 빼주면 된다.

이는 가장 긴 증가하는 부분 수열을 구하는 것이기 때문에 동적계획법으로 간단히 구할 수 있다.

코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());

		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = Integer.parseInt(br.readLine());

		int[] d = new int[n];
		d[0] = 1;
		int ans = 1;
		for (int i = 1; i < n; i++) {
			d[i] = 1;
			for (int j = 0; j < i; j++) {
				if (a[j] < a[i])
					d[i] = Math.max(d[i], d[j] + 1);
				ans = Math.max(ans, d[i]);
			}
		}

		bw.write((n - ans) + "");
		bw.flush();
		bw.close();
	}
}