이코테 - 병사 배치하기 with JAVA

 

 

해결

전투력이 높은 순서대로 배열을 설정하기 위해 몇몇의 병사들을 제거하여 이를 설정하려고 하는데, 최대한 병사를 적게 줄여야한다.

 

전투력이 15 11 4 8 5 2 4라고 가정하자.

뒤에서부터 DP를 적용한다.

- 전투력이 4인 병사에서 살릴 수 있는 병사의 수는 1이다. 

- 전투력이 2인 병사에서 4보다 작으므로 살릴 수 있는 병사의 수는 1이다.

- 전투력이 5인 병사에서 2보다 크므로 병사 2에서 살릴수 있는 병수+1이고 마찬가지로 4에도 적용된다.

 

즉, 로직을 보면 뒤부터 진행을 하는데 이미 처리한 병사들 중 현재 전투력보다 작다면 해당 병사가 갖는 최대 병사+1 처리를 해주면 된다.

 

 

 

 

 

코드

import java.util.*;

public class Q4 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer> soldiers = new ArrayList<>();
        for(int i=0; i<n; i++){
            soldiers.add(sc.nextInt());
        }
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int max_value = 1;
        for(int i=n-2; i>=0; i--){
            for(int j=i+1; j<n; j++){
                if(soldiers.get(j) < soldiers.get(i)){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                    max_value = Math.max(max_value, dp[i]);
                }
            }
        }
        System.out.println(n-max_value);
    }
}