[백준] 1026. 보물 (Java)

문제 : https://www.acmicpc.net/problem/1026

1026번: 보물

 

 

풀이

// [백준] 1026. 보물 (Java)
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 Main{
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(in.readLine()); 
		ArrayList<Integer> arrA = new ArrayList<>();
		ArrayList<Integer> arrB = new ArrayList<>();
		int sum = 0;
		
		StringTokenizer a = new StringTokenizer(in.readLine());
		StringTokenizer b = new StringTokenizer(in.readLine());
		
		for(int i = 0; i<n; i++) {
			arrA.add(Integer.parseInt(a.nextToken()));
			arrB.add(Integer.parseInt(b.nextToken()));
		}
		
		for(int i = 0; i<n; i++) {
			// A의 최솟값과 B의 최댓값의 곱
			int min = Collections.min(arrA);
			int max = Collections.max(arrB);
			// 누적
			sum += (min * max);
			
			// 게산한 값 제외시킴
			arrA.remove(Integer.valueOf(min));
			arrB.remove(Integer.valueOf(max));
		}
		
		System.out.println(sum);
		in.close();
	}
}

두 배열의 원소들끼리 각각 곱했을때 수가 가장 작으려면

(A에서 가장 작은 값 * B에서 가장 큰 값) 을 반복해서 찾아서 합하면 된다.

한번 계산한 쌍은 제외시켜주면서 n번 반복하면 최솟값을 구할 수 있다.