백준 18353 병사 배치하기

문제

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

---

출력

---

예제

---

태그

• 다이나믹 프로그래밍
• 가장 긴 증가하는 부분 수열: o(n log n)

---

풀이

병사가 n명일 때마다 최대로 저장할 수 있는 병사의 수를 배열 dp로 설정한다.

이중 for문을 사용하여 dp배열을 채운다.

내림차순으로 정렬하여야하므로 앞의 병사가 자신보다 전투력이 높을 때에만 앞의 병사 + 1을 하여 dp배열을 채운다.

---

코드

정답 코드

package dp;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P_18353 {
    static int N;
    static int[] soldier; // 전투력 입력 배열
    static int[] dp; // i번째 병사 배치할 때 최대 병사 수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        soldier = new int[N];
        dp = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for (int i = 0; i < N; i++) {
            soldier[i] = Integer.parseInt(st.nextToken());
        }
        dp[0] = 1;

        for (int i = 1; i < soldier.length; i++) {
            int max = 0;
            for (int j = i-1; j >= 0; j--) {
                if(soldier[j] > soldier[i]){
                    max = Math.max(max, dp[j]);
                }
            }
            dp[i] = max + 1;
        }

        int max = 0;
        for(int val : dp){
            if(max < val){
                max = val;
            }
        }

        System.out.println(N - max);
    }
}

---