[BOJ] 백준 1026 - 보물(JAVA)

문제에서 A에 대해서만 재배열 시키라고 했는데, 다르게 생각해서

최소값을 구하는 문제라서 하나는 오름차순 나머지는 내림차순으로 정렬 시켜서 곱의 최소값을 구했습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main1026_보물2 {
    private static int[] A;
    private static Integer[] B;
    private static int minNum = Integer.MAX_VALUE;
    private static int N;
    private static ArrayList<Integer> list;
    private static boolean[] visited;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine().trim());
        A = new int[N];
        visited = new boolean[N];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine(), " ");
        B = new Integer[N];
        list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            B[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(A);
        Arrays.sort(B, Collections.reverseOrder());
        int result = 0;
        for (int i = 0; i < A.length; i++) {
            result += A[i]*B[i];
        }
        System.out.println(result);
    }
 
}
 

 

 

밑에는 B는 그대로 냅두고, A를 순열을 이용해서 최소값을 구하려고 했지만, 시간초과로 인해서 위의 방법으로 풀었습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main1026_보물 {
    private static int[] A;
    private static int[] B;
    private static int minNum = Integer.MAX_VALUE;
    private static int N;
    private static ArrayList<Integer> list ;
    private static boolean[] visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine().trim());
        A = new int[N];
        visited = new boolean[N];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine(), " ");
        B = new int[N];
        list =new ArrayList<>();
        for (int i = 0; i < N; i++) {
            B[i] = Integer.parseInt(st.nextToken());
        }
        perm(0);
        System.out.println(minNum);
    }
    
    public static void perm(int idx) { //순열
        if(idx == N) {
            int result = 0;
            for (int i = 0; i < N; i++) {
                result += list.get(i)*B[i];
                if(result > minNum) return;
            }
            minNum = minNum > result ? result : minNum;
            return;
        }
        
        for (int i = 0; i < N; i++) {
            if(!visited[i]) {
            list.add(A[i]);
            visited[i] = true;
            perm(idx+1);
            visited[i] = false;
            list.remove(list.size()-1);
            }
        }
    }
    
    
    
    
    
}