[백준 / BOJ] 1026번 : 보물 JAVA

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

1026번: 보물

1026번 : 보물 [수학, 그리디 알고리즘, 정렬]

 

이번 문제의 아이디어는 '가장 큰 수와 가장 작은 수를 곱해야 한다' 는 것이다.

 

문제에는 A 배열은 순서를 바꿔도 되지만 B 배열은 바꾸면 안된다고 명시해두었는데, A와 B의 곱셈을 더하는 것으로 이뤄진 이 문제에서 A 배열의 순서를 바꿀 수 있다면 B의 순서를 내버려두는 것은 큰 의미가 없다. 즉, 공식이나 순서까지 출력하라는 것이 아니면 B 역시 바꿔버려도 알 수 없는 것이다.

 

이에 따라 배열 A와 B를 정렬하고 곱하도록 만들었다. 단 A의 가장 작은 수와 B의 가장 큰 수가 만나도록 해야하기 때문에, A[i] * B[N - i - 1] 으로 작성하였다.

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] A = new int[N];
		int[] B = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringTokenizer st2 = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
			B[i] = Integer.parseInt(st2.nextToken());
		}
		
		long total = 0l;
		
		Arrays.sort(A);
		Arrays.sort(B);
		
		for (int i = 0; i < N; i++) {
			total += A[i] * B[N - i - 1];
		}
		
		System.out.println(total);
	}

}