[BaekJoon] 1026 보물

1.  문제 링크

2.  문제

요약

• 길이가 같은 정수 배열 A와 B의 원소들을 곱한 후 더하는데 B의 수는 재배치하지 않고 A의 수를 재배치해서 같은 위치에 있는 원소들을 각각 곱한 후 더한 값의 최솟값을 구합니다.
• 입력: 첫 줄은 정수 배열의 길이가 주어지고 두 번째 줄에는 배열 A의 원소들, 세 번째 줄에는 배열 B의 원소들이 주어집니다.
• 출력: 곱한 값의 최솟값을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	public int makeMinMultiply(ArrayList<Integer> list_a, ArrayList<Integer> list_b) {
		Collections.sort(list_a);
		Collections.sort(list_b, Collections.reverseOrder());
		int result = 0;
		for(int i = 0; i < list_a.size(); i++) {
			result += list_a.get(i) * list_b.get(i);
		}
		return result;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
		ArrayList<Integer> list_a = new ArrayList<Integer>();
		ArrayList<Integer> list_b = new ArrayList<Integer>();
		String a_nums = br.readLine();
		StringTokenizer st = new StringTokenizer(a_nums);
		while(st.hasMoreTokens()) {
			list_a.add(Integer.parseInt(st.nextToken()));
		}
		String b_nums = br.readLine();
		st = new StringTokenizer(b_nums);
		for(int i = 0; i < num; i++) {
			list_b.add(Integer.parseInt(st.nextToken()));
		}
		Main m = new Main();
		System.out.println(m.makeMinMultiply(list_a, list_b));
	}
}

4.  접근

• 각 원소들을 곱한 후 더해서 최솟값을 만드려면 큰 값과 작은 값들을 순서대로 곱한 후 더해야 최솟값을 만들 수 있습니다.
• B의 원소들은 재배치할 수 없으므로 A의 원소들을 B의 큰 수와 A의 작은 수가 매칭되게끔 재배치하여 최솟값을 만들면 됩니다.
• 문제에서는 B의 원소를 재배치하면 안된다고 하였지만 A의 작은 수와 B의 큰 수가 매칭되게끔 A는 오름차순 정렬, B는 내림차순 정렬을 한 후에 이를 원래 B의 순서대로 재배치하면 B는 재배치하지 않고 A만 재배치한 셈이 됩니다.
• 우리는 배열의 순서도 같이 출력하는 것이 아닌 최솟값만 출력하는 것이므로 원래 B의 순서대로 재배치하는 것은 생략합니다.
• A와 B를 재배치한 것을 같은 위치에 있는 원소들끼리 곱한 후 더하면 최소값이 되므로 이를 출력합니다.