[BOJ 18353] 병사 배치하기 (Java, DP, LIS)

 

---

문제 링크

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

18353번: 병사 배치하기

---

문제 풀이 

- DP, LIS (Longest Incresing Subsequence, 최장 증가 부분 수열) 

- 시간 복잡도 O(N^2)

- 단순히 LIS 최대 길이를 구한 후 N과 차이를 구하면 되는 문제라서 DP 배열을 순차적으로 갱신 해준다 

 

(1) 입력된 배열을 reverse함 

(2) DP 배열을 1로 초기화함 (숫자 자신을 가르킴)

(3) 순차 조회하면서 앞에 숫자 중에 자기보다 작은 숫자가 있으면 갱신

 

reverse	4	2	5	8	4	11	15
DP	1	1	2	3	2	4	5

---

제출 코드 

import java.util.*;
import java.io.*;

public class Main {
    
    static int N;
    static int[] DP;

    static List<Integer> DATA = new ArrayList<>();

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            DATA.add(Integer.parseInt(st.nextToken()));
        }

        br.close();
    }

    static void pro() {
        Collections.reverse(DATA);

        DP = new int[N];
        Arrays.fill(DP, 1);

        for(int i = 1; i < N; i++) {
            for(int j = 0; j < i; j++) {
                if(DATA.get(i) > DATA.get(j)) DP[i] = Math.max(DP[i], DP[j] + 1);
            }
        }

        int maxValue = Arrays.stream(DP).max().getAsInt();
        System.out.println(N - maxValue);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}