[이코테][Java] 병사 배치하기

[문제 링크]

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

---

문제 설명

N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있고, 병사를 배치할 때는전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다.

배치 과정에서는 특정 위치에 있는 병사를 열외시키는 방법을 이용하고, 남아있는 병사의 수가 최대가 되도록 하고자 한다.

병사에 대한 정보가 주어졌을 때, 병사의 수가 최대가 되도록 하기 위해서 열외시켜야 하는 병사의 수를 출력하는 프로그램을 작성하시오.

 

입력조건

• 첫째 줄에 병사의 수 N
• 둘째 줄에 각 병사의 전투력

출력조건

• 남아있는 수가 최대가 되도록 하기 위해서 열외시켜야 하는 병사의 수 

입출력 예시

입력예시	출력예시
7 15 11 4 8 5 2 4	2

 

 

 

 

문제 풀이

• 다이나믹 프로그래밍으로 풀이
• 가장 긴 증가하는 부분 수열의 풀이와 비슷하다.
• 여기에서는 전투력이 내림차순이 되도록 배치하기 때문에 가장 긴 감소하는 부분 수열이다.
• dp[i] 는 array[i]를 마지막 값으로 가지는 가장 긴 감소 부분 수열의 길이
• array[0]~array[i-1]와 array[i]를 비교해서 (array[i] < array[j]를 만족하는 dp[j]값들 중에서 가장 큰 값) + 1 한 값이 dp[i]가 된다.
• 열외시켜야 하는 병사의 수 = n - (dp 테이블에서 가장 큰 값)

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));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());    //병사 수

        int[] array = new int[n + 1];   //병사의 전투력
        int[] dp = new int[n + 1];  //전투력을 내림차순으로 배치하는 최대 병사의 수를 계산하는 dp 테이블

        //전투력 입력
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            array[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (array[i] < array[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int max = Arrays.stream(dp).max().getAsInt();   //최대 병사의수 구하기
        System.out.println(n - max);
    }
}

---

[참고서적]

이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈