백준 1026번, 보물

문자열 문제만 풀다가 최근 들어 그리디 문제도 손 대기 시작하였습니다.
종종 업데이트 할 예정입니다.

A만 재배열 가능하고 ,B는 재배열이 불가능합니다.
하지만, 귀찮기 때문에 둘 다 재배열하였습니다.

A[i] * B[i]의 최소값으로 생각할 수 있는 경우는

1) A 최소값 B 최소값 --> A의 최대값 B의 최대값으로 이어집니다.
2) A 최소값 B 최대값 --> A의 최대값 B의 최소값으로 이어집니다.
입니다. 그런데 의 경우, 최대값 최대값은 상상할 수 없는 결과로 이어질 수 있습니다.
B의 최대값을 A의 최소값으로 상쇄시키고 A의 최대값을 B의 최소값으로 상쇄시켜야 합산 최소값이 나올 수 있을 것 같습니다.

--> A는 오름차순으로 정렬, B 지갑은 내림차순으로 정렬 후 같은 자리의 원소끼리 곱합니다.

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
		int cnt = Integer.valueOf(bfr.readLine());
		int result = 0;
		Integer[][] arr = new Integer[2][cnt];

		for (int i = 0; i < 2; i++) {
			StringTokenizer st = new StringTokenizer(bfr.readLine());
			for (int j = 0; j < cnt; j++)
			 arr[i][j] = Integer.valueOf(st.nextToken());
		}

		Arrays.sort(arr[0]);
		Arrays.sort(arr[1], Collections.reverseOrder());
		
		for(int i =0; i < cnt; i++) {
			result += arr[0][i] * arr[1][i];
		}
		System.out.println(result);
		
		bfr.close();
	}
}