[BaekJoon] 2631 줄세우기

1.  문제 링크

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

2.  문제

요약

• 1번부터 N번까지 번호가 적혀있는 번호표를 붙이고 있는 아이들이 임의대로 서서 걸어가고 있습니다.
• 아이들을 번호 순서대로 줄을 세우려고 하는데 위치를 옮기는 아이들의 수를 최소로 하려고 합니다.
• 임의의 순서로 줄을 서 있는 N명의 아이들을 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 200보다 작거나 같은 아이들의 수 N이 주어지고 두 번째 줄부터 N개의 줄에는 숫자가 한 줄에 하나씩 주어집니다.
• 출력: 첫 번째 줄에 번호 순서대로 줄을 세우는데 옮겨지는 아이들의 최소 수를 출력합니다.

3.  소스코드

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

public class Main {
	static int[] nums;
	int[] dp;
	public int getMinNum() {
		int max = 0;
		dp = new int[nums.length];
		Arrays.fill(dp, 1);
		for(int i = 1; i < nums.length; i++) {
			for(int j = 0; j < i; j++) {
				if(nums[j] < nums[i]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
			max = max < dp[i] ? dp[i] : max;
		}
		return nums.length - max;
	}
	
	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 people_num = Integer.parseInt(br.readLine());
		nums = new int[people_num];
		for(int i = 0; i < people_num; i++) {
			nums[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		Main m = new Main();
		bw.write(m.getMinNum() + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 LIS/DP를 이용하여 해결할 수 있습니다.

LIS 알고리즘

• LIS, Longest Increasing Subsequence(최장 증가 부분 수열) 알고리즘은 원소가 n개인 배열의 일부 원소들을 골라 만든 부분 수열 중, 각 원소가 이전 원소보다 크고 그 길이가 최대인 부분 수열인 최장 증가 부분 수열을 찾는 알고리즘입니다.
• 일반적으로 LIS의 길이가 얼마인지 푸는 문제는 DP를 이용하여 해결합니다.
• 주어진 배열에서 인덱스를 하나씩 늘려가면서 해당 인덱스보다 작은 인덱스들을 확인하여 자신보다 작은 숫자들이 있을 경우 해당 인덱스에서 자신보다 작은 숫자들의 개수를 나타내는 변수의 값을 1 증가시킵니다.

for(int i = 0; i < n; i++) {
	length[i] = 1;
    for(int j = 0; j < i; j++) {
    	if(arr[j] < arr[i]) {
        	length[i] = max(length[i], length[j] + 1);
        }
    }
}

• j번째 인덱스에서 끝나는 LIS의 마지막에 arr[i]를 추가했을 때의 LIS 길이와 추가하지 않은 기존의 length[i] 값 중 더 큰 값으로 length[i] 값을 업데이트합니다.
  

• LIS 알고리즘을 이용하여 현재 주어진 숫자들의 순서에서 LIS의 길이를 구하여 이동시키지 않는 아이들의 수를 구한 후에, 그 아이들을 제외한 아이들을 이동시키면 옮겨지는 아이들의 최소 수를 구할 수 있습니다.
  
  

1. 주어진 수들에 대해 각 위치보다 작은 인덱스들을 확인하여 자신보다 작은 숫자들의 개수를 구하여 저장하는 1차원 배열 변수인 dp를 생성하고 모든 값을 1로 초기화시킵니다. 또한 LIS의 길이를 나타내는 변수인 max의 값을 0으로 초기화합니다.
2. 두 번째 인덱스부터 시작하여 마지막 수까지 확인하면서 dp의 값들을 구하여 LIS의 길이를 구합니다.
   1. 첫 번째 수부터 현재 위치 바로 이전까지의 수들을 확인하여 dp의 값을 구하려는 위치의 수보다 작은 수들이 있다면 구하려는 위치의 dp값을 (현재 dp값)과 (구하려는 위치의 수보다 작은 수의 dp값 + 1) 중 더 큰 값으로 변경합니다.
   2. max의 값을 만약 max의 값이 구하려는 위치의 dp값보다 작다면 구하려는 위치의 dp값으로 변경하고 그렇지 않다면 그대로 max 값을 유지합니다.
3. 주어진 수들의 전체 길이에서 max값을 뺀 값이 옮겨지는 아이들의 최소 수가 되어 해당 값을 출력합니다.