[Silver II] 병사 배치하기 - 18353

문제 링크

성능 요약

메모리: 14644 KB, 시간: 160 ms

분류

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

제출 일자

2024년 3월 28일 14:16:03

문제 설명

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

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

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

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

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

입력

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

출력

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

코드 (DP 풀이)

이 풀이는 열외하는 병사를 직접적으로 구하는 것이 아닌, 전체 병사의 수에서 정상적인 병사의 수를 빼는 방식으로 해결하는 풀이이다.

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

public class Main {
	//문제 의도: 열외해야 하는 병사의 수를 직접적으로 구하는 것이 아닌, 전체에서 정상 병사의 수를 빼서 계산
	static int size; //병사의 수
	static long[] dp;
	static long[] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		size=Integer.parseInt(br.readLine());
		dp=new long[size+1];
		arr=new long[size+1];
		StringTokenizer st = new StringTokenizer(br.readLine());
		//병사 배열 + dp 배열 설정
		
		for(int i=1;i<=size; i++) { //병사 전투력 입력 + dp 1 입력
			arr[i]=Integer.parseInt(st.nextToken());
			dp[i]=1;
		}
		
		for(int i=1; i<=size; i++) {
			for(int j=1; j<i; j++) {
				if(arr[i]<arr[j]) {//예를 들어 3번째 값보다 4번째 값이 더 작다면? ->정상이라면?
					dp[i]=Math.max(dp[i],dp[j]+1 );//dp값 더 큰거 고르기
				}
			}
		}
		long max_dp=0;
		for(int i=1; i<=size; i++) {
			if(dp[i]> max_dp) {
				max_dp=dp[i];//가장 큰 dp값 찾기
			}
		}
		System.out.println(size-max_dp);//전체 - 정상적인 병사 수 = 열외해야 하는 병사 수
	}
}

문제 풀이 순서
1. 병사 N명을 입력받는다.
2. 각각의 병사 전투력을 배열에 넣어줌과 동시에 DP배열에 1이라는 값을 넣어준다.
2-1. 여기서 1은 나중에 정상 범위를 차근차근 늘려가기 위함이다.
3. 이중 for문으로 정상 병사인지 아닌지 판별 후 DP값이 더 큰 것을 찾아 넣어준다.
4. 가장 큰 dp값 (가장 큰 정상 범위)를 찾고 max_dp 변수에 넣어준다.
5. 전체 N(size)에서 max_dp를 빼준 값이 답이 된다.