[Baekjoon] 18353_병사 배치하기

문제(출처: https://www.acmicpc.net/problem/18353)

---

< 병사 배치하기 >

 

문제 풀이 

 

dp를 활용하여 남아있는 병사의 수가 최대가 되도록 구한다.

 

my solution (Java)

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

public class _18353_ { // 병사 배치하기

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

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

		int arr[] = new int[n];
		int dp[] = new int[n];

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

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

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

		System.out.println(n - max);

	}
}

변수)
n : 병사 수
arr : 병사의 전투력
dp : 남아있는 병사의 수
max : 남아있는 병사의 최대 수

 

병사 수를 입력받는다. 병사 수만큼 병사의 전투력을 입력받아 arr에 저장하고 dp를 1로 초기화한다. 현재 위치에서 앞을 살펴보며 전투력이 앞보다 작다면 값을 업데이트한다. 

 

최종 dp를 살펴보며 최댓값을 구해 n-max를 출력한다. 

---

---