백준 18353 java : DP, LDS

LIS와 LDS의 개념에 대해 공부하고 적용할 수 있었다.

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

public class bj18353 {
    static Scanner scanner = new Scanner(System.in);
    static int[] trooper;

    public static void main(String[] Args){
        inputData();
        System.out.println(findAnswer());

        scanner.close();
    }

    public static void inputData(){
        System.out.println("\ninputData()");
        int N, i;

        N = scanner.nextInt();
        trooper = new int[N];
        for(i = 0; i < N; i++){
            trooper[i] = scanner.nextInt();
        }
    }

    public static int findAnswer(){
        System.out.println("\nfindAnswer()");
        int i, j,  maxLength = 0, N = trooper.length;
        int[] DP = new int[N];
        //전투력이 내림차순이면서, 남아있는 병사 수가 최대가 되도록 하기
        //LDS : 최장 감소 부분 수열 문제 <-> LIS : 최장 증가 부분 수열

        Arrays.fill(DP, 1);//각 병사는 자신만으로도 길이가 1이 됨

        for(i = 0; i < N; i++){
            for(j = 0; j < i; j++){
                if(trooper[j] > trooper[i]){//오른쪽으로 갈수록 감소한다면?
                    DP[i] = Math.max(DP[i], DP[j] + 1);
                }
            }

            for(int temp : DP) {
                System.out.print(temp + " ");
            }
            System.out.println();
        }

        //최대 길이 계산
        for(i = 0; i < N; i++){
            maxLength = Math.max(maxLength, DP[i]);
        }

        return N - maxLength;
    }
}