[BOJ 14718] 용감한 용사 진수

[풀이 코드]

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

public class Main {
	static int N, K;
	static int[][] arr;
	static int p, d, t;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		arr = new int[N][3];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 3; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int result = Integer.MAX_VALUE;
		for (int i = 0; i < N; i++) {
			p = arr[i][0];
			for (int j = 0; j < N; j++) {
				d = arr[j][1];
				PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
				for (int k = 0; k < N; k++) {
					t = arr[k][2];
					if(arr[k][0] <= p && arr[k][1] <= d) {
						pq.offer(t);
						if(pq.size()>K) {
							pq.poll();
						}
					}
					
					if(pq.size()==K) {
						int min = pq.peek();
						result = Math.min(result, p+d+min);
					}
				}
				
			}
			
		}
		System.out.println(result);
	}
}

p는 힘이고, d는 민첩, t는 지능이다.

3중 for문을 이용해 모든 경우의 수를 확인한다.

예를 들어,
입력이 아래와 같이 주어졌다면,

3 1
234 23 342
35 4634 34
46334 6 789

234 23 342
234 23 34
234 23 789
234 4634 342
234 4634 34
...
이런 규칙대로, p, d, t에 값이 새로 갱신된다.

이 과정에서 3중 for문 중 마지막 for문에서 k 위치에 있는 힘, 민첩이 i 위치에 있는 힘인 p, j 위치에 있는 민첩인 d보다 작거나 같으면 t를 pq에 넣는다.
그리고 pq의 size가 이겨야 할 병사 수인 K보다 크면 pq.poll()을 통해 인트가 가장 큰 값을 pq에서 빼내고, K랑 같아지면 result 값을 갱신한다.
p + d + pq.peek() 로 갱신하는 이유는 이겨야 할 병사 수가 K이고, 최소의 스탯 포인트를 구해야 하므로 p와 d 그리고 pq에서 인트가 가장 큰 값을 더한 값을 result와 비교해서 최솟값으로 갱신한다.