34.병사 배치하기

📍 문제 설명

 

💡 접근

바로 뒤쪽이 아닌 모든 뒤쪽 병사들의 전투력보다 커야한다.

뒤집어서 LIS 알고리즘을 적용해서 최장 증가 부분 수열의 길이를 구하고

병사의 수 - 길이를 해주면 남아있는 병사의 최대 수가 나온다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();
        ArrayList<Integer> v = new ArrayList<Integer>();
        int[] dp = new int[n];
        for(int i = 1; i <= n; i++) {
            v.add(kb.nextInt());
        }
        Collections.reverse(v);

        //i번째 인덱스의 값을 마지막 항으로 하는 최대 증가 수열의 길이를 담는 dp 테이블 초기화
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }

        // 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (v.get(j) < v.get(i)) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        //열외해야 하는 병사의 최소 수 출력
        int max = 0;
        for(int i = 0; i < n; i++) {
            max = Math.max(max, dp[i]);
        }
        System.out.println(n - max);
    }
}