[BOJ/Java] 백준 18353번 - 병사 배치하기

백준 #18353 병사 배치하기

18353번: 병사 배치하기

 

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		
		// 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int[] power = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			power[i] = Integer.parseInt(st.nextToken());
		}
	
		int[] dp = new int[N];
		dp[0] = 1;
		int max = 1;
		for (int i = 1; i < N; i++) {
			dp[i] = 1;
			for (int j = i-1; j >= 0; j--) {
				if (power[i] >= power[j]) continue;
				dp[i] = Math.max(dp[i], dp[j]+1);
				max = Math.max(max, dp[i]);
			}
		}
        
		System.out.println(N - max);
	
		
	}  // end of main
}  // end of class

dp로 풀었다. dp에는 앞에서부터 자기 자리에 오기까지 배치할 수 있는 병사의 최대 수를 저장하게 된다. 앞에 있는 병사가 자신보다 전투력이 강하다면 그 병사 뒤에 설 수 있는 것으로 해당 병사까지의 병사 최대 수 + 1을 저장해준다. 즉 dp[i] = dp[i-1]+1 이라는 점화식을 세울 수 있는데, 앞에 있는 병사들 중 어떤 병사의 뒤에 섰을 때 최대 수인지 모두 비교해봐야 하기 때문에 이중 for문을 통해 모든 수들을 비교해준다. 따라서 dp[i] = Math.max(dp[i], dp[j]+1) 라는 식을 세울 수 있다. 이때, 배치할 수 있는 병사의 최솟값은 자기 혼자 서있을 경우인 1이기 때문에 for문을 돌 때 dp[i] = 1로 초기화가 필요하다.