문제
N명의 적이 각각 힘(S), 민첩(D), 지능(I) 스탯을 가지고 있다. 용사 진수의 세 스탯이 모두 적의 스탯 이상이면 그 적을 이길 수 있을 때, K명 이상을 이기기 위한 S+D+I 합의 최솟값을 구하라.
입력
첫째 줄에 N, K가 주어진다. 다음 N줄에 각 적의 S, D, I가 주어진다.
출력
K명 이상을 이길 수 있는 S+D+I의 최솟값을 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 3 1 1 1 2 2 2 3 3 3 | 9 |
풀이
최적의 스탯 값은 반드시 적들의 스탯 값 중 하나와 같다는 관찰을 활용하여 브루트포스로 풀이한다.
- 모든 적을 지능(I) 기준 오름차순으로 정렬한다
- 힘(S)과 민첩(D)의 후보값을 모든 적의 S, D 값에서 선택한다 (N^2 조합)
- 선택된 (S, D) 조합에 대해, 정렬된 적 목록을 순회하며
S >= 적.S && D >= 적.D인 적을 센다 - K명에 도달하는 순간의 I값을 사용하여 S+D+I의 최솟값을 갱신한다
핵심 아이디어: 진수의 최적 스탯은 항상 어떤 적의 스탯과 일치하므로, 후보를 적의 스탯 값으로 제한할 수 있다. 지능을 오름차순 정렬해두면 조기 종료가 가능하다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Day71BOJ14718용감한용사진수반복문단축 {
static int N, K, ans;
static List<int[]> list;
static PriorityQueue<int[]> pq;
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());
ans = 3_000_000;
list = new LinkedList<>();
pq = new PriorityQueue<>((o1, o2) -> (o1[2] - o2[2]));
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
pq.add(new int[] { Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken()) });
}
while (!pq.isEmpty()) {
list.add(pq.poll());
}
for (int l = 0; l < N; l++) {
for (int j = 0; j < N; j++) {
int s = list.get(l)[0], d = list.get(j)[1];
int i = 0, c = 0;
for (int[] a : list) {
if (s >= a[0] && d >= a[1]) {
i = a[2];
c++;
}
if (c == K) {
ans = Math.min(ans, s + d + i);
break;
}
}
}
}
System.out.println(ans);
br.close();
}
}복잡도
- 시간: O(N³)
- 공간: O(N)