[BOJ/Java] 14718 용감한 용사 진수 - 요소에 대해 완전탐색

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42895

풀이

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

public class Main {

    public static void main(String[] args) throws IOException {
    	
    	// 1억 = 100,000,000 = Math.pow(10, 8);
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	int N = Integer.parseInt(st.nextToken());
    	int K = Integer.parseInt(st.nextToken());
    	
    	int[][] soldiers = new int[N][3];
    	int[] powers = new int[N];
    	int[] speeds = new int[N];
    	int[] intels = new int[N];
    	for (int i=0; i<N; i++) {
    		st = new StringTokenizer(br.readLine());
    		soldiers[i][0] = Integer.parseInt(st.nextToken());
    		soldiers[i][1] = Integer.parseInt(st.nextToken());
    		soldiers[i][2] = Integer.parseInt(st.nextToken());
    		powers[i] = soldiers[i][0];
    		speeds[i] = soldiers[i][1];
    		intels[i] = soldiers[i][2];
    	}
    	
    	Arrays.sort(powers);
    	Arrays.sort(speeds);
    	Arrays.sort(intels);
    	
    	int ans = Integer.MAX_VALUE;
    	for (int power : powers) {
    		if (power <= ans) {
    			for (int speed : speeds) {
    				if (power+speed <= ans) {
    					outer: for (int intel : intels) {
    						if (power+speed+intel <= ans) {
    							int cnt = 0;
    							for (int[] soldier : soldiers) {
    								if (power >= soldier[0] && speed >= soldier[1] && intel >= soldier[2]) {
    									cnt++;
    									if (cnt == K) {
    										ans = Math.min(ans, power+speed+intel);
    										break outer;
    									}
    								}
    							}
    						}
    					}
    				}
    			}
    		}
    	}
    	
    	System.out.print(ans);
    }
    
};

배운 점

• 시간 복잡도 줄이는 아이디어를 떠올리는데 애먹은 문제였다.
• 완전히 완전탐색하면 1,000,000 ** 3 이어서 시간초과 날 것이 뻔하고, 최대, 최소 범위로 제한해서 약간 최적화하는 것도 소용 없을 것 같지만 달리 방도가 떠오르지 않았다.
• array에 값을 담고 정렬해서 array의 요소만을 대상으로 완전탐색하면 된다!