[Algorithm] 병사 배치하기

문제

N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치하고자 한다.

 

또한 배치 과정에서 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아 있는 병사의 수가 최대가 되도록 한다.

 

병사에 대한 정보가 주어졌을 때, 남아 있는 병사의 수가 최대가 되도록 하기 위해서 열외시켜야 하는 병사의 수를 출력하는 프로그램을 작성하시오.

 

풀이

문제에서는 전투력이 강한 순서대로 세웠지만 이를 반대로 약한 순서대로 세워도 문제 없다.

약한 순서대로 오름차순으로 봤을 때, 해당 문제는 최장 증가 부분 수열 문제로 볼 수 있다.

[Algorithm] 최장 증가 부분 수열 (LIS)

 

먼저 주어진 병사의 정보를 역순으로 정렬한 후, 최장 증가 부분 수열 알고리즘을 적용하여 가장 긴 부분 수열의 길이를 전체 병사 수에서 빼주면 열외된 인원의 수가 나온다.

 

전체 소스 코드

import java.util.*;

public class Main {

    public static int n;
    public static List<Integer> list = new ArrayList<>();
    public static int[] dp = new  int[2001];

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        for (int i = 0 ; i < n; i++) {
            list.add(sc.nextInt());
            dp[i] = 1; // 기본으로 부분 수열의 최소 길이
        }

        Collections.reverse(list);

        int result = dp[0];

		// 부분 수열의 갯수 i개
        for (int i = 1; i < n; i++) {
            // 0 ~ i-1까지 확인하면서 i번째 값보다 작은 값에 대해
            for (int j = 0; j < i; j++) {
                if (list.get(j) < list.get(i)) {
                    // 최대값 갱신
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(result, dp[i]);
        }

        // 열외 병사 수 = 전체 - 뽑힌 병사
        System.out.println(n - result);


    }
        
}