DP - 병사 배치하기

문제

이것이 취업을 위한 코딩테스트다 with 파이썬 (https://youtu.be/5Lu34WIx2Us)

• N명의 병사가 무작위로 나열, 각 병사는 특정 값의 전투력을 보유
• 병사를 배치할 때 전투력 내림차순으로 배치하고자 함 (전투력이 높은 순)
• 배치 과정에서 특정한 위치에 있는 병사를 열외시키는 방법을 이용
  이때 남아 있는 병사의 수가 최대가 되도록 하고 싶다.
• 병사에 대한 정보가 주어졌을 때, 남아 있는 병사의 수가 최대가 되도록 하기 위해서 열외시켜야 하는 병사의 수를 출력하는 프로그램을 작성하시오.

 

입력 조건

• 첫째 줄에 병사의 수 N이 주어짐 (1 <= N <= 2,000)
• 둘째 줄에 각 병사의 전투력이 공백으로 구분되어 차례대로 주어짐 (전투력 <= 10,000,000)

 

출력 조건

• 첫째 줄에 남아 있는 병사의 수가 최대가 되도록 하기 위해서 열외시켜야 하는 병사의 수를 출력

 

풀이

• 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence) 알고리즘을
  가장 긴 감소하는 부분 수열을 찾는 문제로 치환해서 풀이할 수 있음
• LIS 알고리즘 점화식
  D[i] = array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이
  모든 0 <= j < i 에 대하여, D[i] = max(D[i], D[j]+1) if array[j] < array[i]
• LIS와 달리 감소하는 형태를 띄어야 하기 때문에 if array[j] > array[i] 으로 값 갱신 조건 변경

 

코드

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

// 병사 배치하기
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        // 병사의 전투력 입력 받기
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        // DP 테이블 초기화
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        // DP Bottom-Up
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[i])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }

        int maxVal =0;
        for(int val : dp){
            maxVal = Math.max(maxVal, val);
        }

        // 전체 - 최장 감소 부분 값 = 열외해야 하는 병사의 최소 수
        System.out.println(n - maxVal);
    }
}