[백준][BOJ-2631][자바] 줄세우기

www.acmicpc.net/problem/2631

2631번: 줄세우기

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		int[] dp = new int[N];
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		for (int i = 0; i < N; i++) {
		    dp[i] = 1;
		    for (int j = 0; j < i; j++) {
		        if (arr[i] > arr[j]) {
		            if (dp[i] < dp[j] + 1) {
		                dp[i] = dp[j] + 1;
		            }
		        }
		    }
		}
			
		System.out.println(N-Arrays.stream(dp).max().getAsInt());
	}
}

 

정리

먼저 아이들의 수를 최소한 움직이려면 어떻게 해야 할까? 반대로 생각하면 아이들을 최대한 안 움직일 수 있는 방법을 찾는 것이다. 

문제에서 3 7 5 2 6 1 4 를 보자 3 5 6을 고정하고 나머지를 옮기면 최소로 옮길 수 있다. 따라서 아이들 중에 고정할 수 있는 어린이 인원수의 최댓값을 찾아야 한다 그러면 각 아이들 자리에서 증가하는 숫자를 찾고 그중 최대 길이를 찾는 최장 증가수열 (LIS)를 적용한다면 쉽게 풀 수 있다.

• 먼저 자기 자신은 포함해야 되기 때문에 dp[i] == 1로 초기화해준다.
• 그다음 자기 자신보다 작은 숫자 중에 최대 길이를 찾기 위해 i까지 반복분 j를 돌린다.
• 만약 자기 자신보다 작은 수가 나온다면 그 자리는 이미 앞에서 최장길이를 구해 놨기 때문에 해당 자리의 dp를 접근해서 +1 (자기 자신)을 했을 때 기존 dp [i] 보다 크다면 갱신해준다.

마지막으로 dp의 최대값이 결국 최대한 안 움직일 수 있는 인원수이고 전체 인원수에서 빼면 그 인원수는 무조건 움직여야 하는 인원이다.