18353 병사 배치하기

병사 배치하기

문제

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

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

예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자.

이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다. 이는 남아있는 병사의 수가 최대가 되도록 하는 방법이다.

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

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력한다.

풀이

LIS를 이용해서 푸는 전형적인 문제이다.
다만 증가하는 수열이 아닌 내림차순임으로 점점 작아지는 것으로 조금만 응용해서 풀면 된다.
입력값의 범위가 1 <= N <= 2000이므로 DP(O(N^2))로 해결해도 된다.

우선 가장 앞의 병사부터 배칠할 수 있는 최댓값(dp[])를 찾는 보텀업 방식으로 진행한다.
가장 앞의 병사는 한명일 때 무조건 자기 자신이므로 1이다.(dp[0] = 1)
2번 병사는 전투력이 1번 병사보다 작을 때 dp[0] + 1 그렇지 않을때 1이다.
3번 병사는 자기보다 앞의 있는 병사들 즉, 1번 병사와 2번 병사 중 자신보다 전투력이 높은 병사를 골라 그 중에서 dp값이 가장 큰 병사의 dp + 1을 하면 된다.
만약 2번 병사가 1번 병사보다 전투력이 크다면 2번 병사의 dp는 1일것이고
반대의 경우네는 2번 병사의 dp는 2일 것이다.
그럼 2번 병사의 전투력에 따라서 3번 병사는 값이 달라진다.
위와 같은 규칙으로 문제를 해결하면된다.

정리하자면 각 병사에 대해서 dp값은 자신의 앞에 있는 병사들 중 자신보다 전투력이 큰 병사의 dp최댓값 + 1이다.

코드

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

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\[\] arr = new int\[n\];  

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

        int\[\] dp = new int\[n\];  
        dp\[0\] = 1;  

        int max = 0;  

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

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

}