백준 - 병사 배치하기(18353) - DP(LIS) - Java

1. 문제

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

2. 풀이

가장 긴 증가하는 부분수열이 생각났다.

따라서 배열을 뒤집어서 가장 긴 증가하는 부분 수열의 길이를 파악하고, 이 길이를 N에서 뺀 값이 답이다.

✨핵심 Point

초기 dp[i] = 1이라는 점이다. 즉 자기 자신을 포함한다고 생각해야 하기 때문이다.

3. 전체 코드

import java.util.*;

public class Main {
    
    public static void main(String args[]) {
        
        Scanner input = new Scanner(System.in);
        
        int N = input.nextInt();
        
        ArrayList<Integer> arr = new ArrayList<Integer>();
        
        for(int n = 0; n < N; n++){
            arr.add(input.nextInt());
        }
        
        Collections.reverse(arr);
        
        int dp[] = new int[N];
        int answer = 0;
        
        for(int i = 0; i < N; i++) {
            dp[i] = 1;
            
            for(int j = 0; j < i; j++) {
                if(arr.get(i) > arr.get(j)) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            
            answer = Math.max(answer, dp[i]);
        }
        
        System.out.println(N - answer);
    }
}