백준 [18353] 병사 배치하기 (자바)

문제

풀이

앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사의 전투력보다 높게 병사를 배치해야 한다.

내림 차순으로 가질 수 있는 가장 긴 수열을 찾는 문제 (LDS)

 

DP를 사용해서 풀이(N 최대가 2000)

1. 0 ~ N - 1 번째 병사까지 탐색
2. dp[i] = 1로 초기화
3. i번째 병사보다 앞에 있는 병사들을 탐색 (0 <= j < i)
4. seq[j] > seq[i] 이고 dp[i] < dp[j] + 1 (dp[j]: j번째까지 최장 수열 길이) 이면 dp[i] = dp[j] + 1 로 갱신
5. max = Math.max(max, dp[i])로 가장 긴 부분 수열 길이를 저장
6. N - max를 출력

정답코드

package com.baekjoon.p18353;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

        int[] dp = new int[N];
        int max = 1;

        for (int i = 0; i < N; i++) {
            dp[i] = 1;

            for (int j = 0; j < N; j++) {
                if (seq[j] > seq[i] && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    max = Math.max(dp[i], max);
                }
            }
        }

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