#2631 : 줄세우기

풀이방법

사용된 것:

다이나믹 프로그래밍(DP)

 

2022.04.05

가장 긴 증가하는 수열의 길이를 구한다.

전체 아이 수에서 해당 수열의 길이를 빼주면 정답이다.

가장 긴 증가하는 수열의 길이를 구할 때에 DP가 사용된다.

 

예를 들면 다음과 같다.

 

3 7 5 2 6 1 4

 

위 수열에서 가장 긴 증가하는 수열은

 

3 7 5 2 6 1 4

 

{3, 5, 6}으로 길이가 3이다.

이 수열에 포함되어있지 않은 7, 2, 1, 4의 자리를 옮겨주어야 하므로 4명의 아이들이 자리를 옮겨야 한다.

따라서 답은 4이다.

 

코드

Java(2022.04.05)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int[] kids = new int[n];
		
		for(int i = 0; i<n; i++) {
			kids[i] = Integer.parseInt(br.readLine());
		}
		
		int[] dp = new int[n];
		Arrays.fill(dp, 1);
		
		//가장 긴 증가하는 수열의 길이 찾기
		for(int i = 1; i<n; i++) {
			for(int j = 0; j<i; j++) {
				if(kids[j]<kids[i]) dp[i] = Math.max(dp[j]+1, dp[i]);
			}
		}
		
		Arrays.sort(dp);
		
		//(전체 어린이 수) - (가장 긴 증가하는 수열의 길이)
		System.out.print(n - dp[n-1]);
	}

}