백준 - 보물 1026

---

방안1. A,B 배열 모두 배치가 가능하다면?

package test;

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

public class Main {


	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int repeat = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		
		Integer[] array_A = new Integer[repeat];
		int[] array_B = new int[repeat];
		for(int i=0; i<repeat; i++) {
			array_A[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine()," ");
		for(int i=0; i<repeat; i++) {
			array_B[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(array_A,Collections.reverseOrder());
		Arrays.sort(array_B);
		int sum=0;
		for(int i=0; i<repeat; i++) {
			sum = sum+(array_A[i]*array_B[i]);
		}
		System.out.println(sum);
	}
}

A를 내림차순 정렬하고 B는 오름차순 정렬하여 곱하여 더해줬다.

 

문제에서 B는 배열을 바꾸지 말라고 했으니 방안2로 가자.

 

방안2

package test;

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int repeat = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int[] array_A = new int[repeat];
		int[] array_B = new int[repeat];
		for (int i = 0; i < repeat; i++) {
			array_A[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < repeat; i++) {
			array_B[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(array_A);

		int sum = 0, point = 0, visit=0;;
		int max = -999999;

		boolean[] visited_B = new boolean[repeat];
		boolean check = true;

		while (check) {
			for (int i = 0; i < repeat; i++) {
				if (visited_B[i] == false) {
					if(max<array_B[i]) {
						max = array_B[i];
						visit=i;
					}
				}
			}visited_B[visit]=true;

			sum = sum + (array_A[point] * max);
			point++;
			
			check=false;
			max = -999999;
			for (int i = 0; i < repeat; i++) {
				if (visited_B[i] == false)
					check = true;
			}

		}
		System.out.println(sum);

	}
}

A만 정렬해주고 B에서 최대값을 찾아줬다

가장 작은값 * 최대값을 곱하니 결과적으로 가장 작은합을 구할 수 있다.

B에서 최대값을 또 넘겨주면 안되니, 방문여부로 체크해줬다.