[BaekJoon/Java] 백준 1026번 보물

문제 요약 설명

배열 A와 배열 B가 각각 같은 사이즈로 존재할때 배열A의 값들과 배열B의 값들을 각각 곱해서 전부 더했을 때 최소합을 구해야 한다

아이디어

배열A만 재배치 가능하고 배열B는 재배치가 불가능하다고 하였으나 결국 A의 가장 작은 값을 B의 가장 큰 값에 곱하는 형태로 합산을 해야 최소 합을 구할 수 있다. 그래서 A와 B를 각각 정렬한 다음 계산하는 형태로 풀어나갈 수 있다.

풀이

1. 배열 A와 배열 B를 각각 sort한다.(둘다 오름차순 정렬하여도 상관없다)
2. 배열 A[0] 배열 B[N-1-0] + 배열 A[1] 배열 B[N-1-1]의 형태로 배열 A[N-1] * 배열 B[0]까지 전부 합한 값을 출력한다.
   (배열 A의 가장작은 값은 0번째 index에 배열 B의 가장 큰 값은 N-1번째 index에 저장되어 있다.)

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = null;

        int[] a = new int[n];
        int[] b = new int[n];

        st = new StringTokenizer(br.readLine());
        for(int j = 0; j < n; j++) {
            a[j] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for(int j = 0; j < n; j++) {
            b[j] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(a);
        Arrays.sort(b);

        int sum = 0;
        for(int j = 0; j < n; j++) {
            sum += (a[j] * b[n-j-1]);
        }
        System.out.print(sum);
        br.close();

    }
}