[백준] 1026번 - 보물 [Java]

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

 

[백준] 1026번 - 보물 [Java]

[백준] 1026번 - 보물 [Java]

---

1.  아이디어

 

S의 최솟값은 작은 수와 큰 수의 곱의 합으로 이루어졌을 때라는 점을 활용한다.

---

2. 문제풀이

 

두 배열에서 가장 큰 수와 가장 작은 수를 매칭시키고 다음으로 큰 수와 다음으로 작은 수를 매칭시키는 과정을 반복하면 되므로 두 배열을 정렬한 후 인덱스를 하나는 정방향, 하나는 역방향으로 순회하며 곱해서 최솟값을 구해준다.

---

3. 코드

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int S = 0;

        // 배열 A 입력 받아서 정렬
        int[] A = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(A);

        // 배열 B 입력 받아서 정렬
        int[] B = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            B[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(B);

        // 큰 수와 작은 수의 곱의 합이 최소
        for (int i = 0; i < N; i++) {
            S += A[i] * B[N - 1 - i];
        }

        System.out.println(S);
    }
}

---

4. 후기