[백준] S2 18353번 병사 배치하기 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

18353번: 병사 배치하기

[문제] 

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

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

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

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

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

[입력]

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

[출력]

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

 

---

[풀이]

1. 입력을 받아 map 배열을 채워준다.

2. 결과를 출력하기 위한 result 변수를 선언해준다.

3. 시작은 무조건 1이므로 dp배열을 1로 채워준다.

4. 현재 값 이전까지 값들을 비교해서 더 큰 값을 찾아준다.

5. 더 큰 값이 나오면 해당 번째의 dp 배열의 값 + 1과 현재 dp 배열의 값을 비교하여 더 큰 것으로 갱신해준다.

6. result에 최대값을 갱신해준다.

7. 모든 배열을 탐색하고 나면 결과를 전체 수에서 뺀 값을 출력해준다.

[접근]

1. 가장 긴 감소하는 부분수열을 구해주고 전체에서 구한 값을 빼주면 되겠다고 생각하였다.

2. 가장 긴 감소하는 부분수열은 아래의 문제를 참고하자.

[백준] S2 11722번 가장 긴 감소하는 부분 수열 (JAVA)

[코드]

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(reader.readLine());

		// 입력 배열
		int[] map = new int[n + 1];
		// dp 배열
		int[] dp = new int[n + 1];

		// 입력 값 채워주기
		StringTokenizer st = new StringTokenizer(reader.readLine());
		for (int i = 1; i <= n; i++) {
			map[i] = Integer.parseInt(st.nextToken());
		}

		// 감소하는 최장길이 부분수열 구하기
		int result = 0;
		for (int i = 1; i <= n; i++) {
			// 시작은 1
			dp[i] = 1;
			for (int j = 1; j < i; j++) {
				// 시작값과 이전값들을 비교
				// 이전 값이 크다면
				if (map[j] > map[i]) {
					// dp[j]는 이전까지 감소하는 부분 수열의 길이
					// 현재 길이와 이전까지 연결된 최대길이 + 1과 비교해서 최대값을 갱신
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
			// 최대 길이 구하기
			result = Math.max(result, dp[i]);
		}

		// 전체 병사 수 - 최장길이 부분수열 = 열외 수
		System.out.println(n - result);
	}
}