문제 정리

---

주어진 순열 두개를 재배치 해서
각 원소간의 곱의 합이
최소가 되게 만들어야 한다

입력

두 정수 배열의 크기 N
정수 배열 A
정수 배열 B

출력

연산 결과중 최솟값

idead 정리

---

각 숫자의 합을 비교하자니 가장 큰 값과 작은 값의 포함 여부를 신경써야해서

오름차순 x 내림차순 한 값과
내림차순 x 오름차순 한 값을 비교해서 더 작은값을 출력하기로 했다

정렬에 걸리는 시간을 최소화하기 위해서 priority queue를 사용했다

알고리즘 정리

---

1. 오름차순 pq과 내림차순 pq에 각 순열을 넣어준다
2. 두 pq가 빌 때까지 pq에서 값을 하나씩 빼서 곱한 값을 더해준다
3. 오름차순에 넣었던 배열은 내림차순에
   내림차순에 넣었던 배열은 오름차순에 넣어서
   2번을 실행해준다
4. 2번의 결과와 3번의 결과를 비교해 작은 값이 결과값이 된다

구현

---

//보물
public class Main {
	static int N;
	static int[] aNums;
	static int[] bNums;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());
		aNums = new int[N];
		bNums = new int[N];
		
		PriorityQueue<Integer> asc = new PriorityQueue<>();		//오름차순
		PriorityQueue<Integer> desc = new PriorityQueue<>(Collections.reverseOrder()); //내림차순
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			int value = Integer.parseInt(st.nextToken());
			aNums[i] = value;
			asc.add(aNums[i]);
		}
		
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			int value = Integer.parseInt(st.nextToken());
			bNums[i] = value;
			desc.add(bNums[i]);
		}
		
		int minRes = Integer.MAX_VALUE;
		
		int sum = 0;
		for(int i=0; i<N; i++) {
			int num1 = asc.poll();
			int num2 = desc.poll();
			sum += num1 * num2;
		}
		minRes = Math.min(minRes, sum);
		
		for(int i=0; i<N; i++) {			//오름, 내림 바꿔서 계산
			desc.add(aNums[i]);
			asc.add(bNums[i]);
		}
		
		sum = 0;
		for(int i=0; i<N; i++) {
			int num1 = asc.poll();
			int num2 = desc.poll();
			sum += num1 * num2;
		}
		minRes = Math.min(minRes, sum);
		
		bw.write(minRes + "");
		bw.flush();
		bw.close();
		br.close();
	}
}

결과

---