[코딩테스트] 백준 1026번: 보물 - JAVA

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

Problem 💻

문제

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0] × B[0] + ... + A[N-1] × B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 S의 최솟값을 출력한다.

 

Solution 💡

문제에서 주어진 조건이다. 이 계산식의 결과값은 S가 최소로 나오는 프로그램을 만드는 것이다.

S = A[0] × B[0] + ... + A[N-1] × B[N-1]

위 문제에서는 A의 수를 재배열이 가능하며, B의 수는 재배열하면 안된다.

• A의 수를 재배열해보면 오름차순 또는 내림차순으로 정렬해야한다는 것을 의미한다. 여기선 오름차순 정렬을 하였다.
• 재배열한 A를 이용한 최소값을 구하기 위해선 A의 가장 작은 수와 B의 가장 큰 수 순으로 짝을 지으면 최소값이 나온다는 것을 유추할 수 있다.
• A를 오름차순 정렬하였기 때문에 B를 내림차순 정렬하여 A의 최솟값과 B의 최대값을 매칭될 수 있게 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
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());

        Integer[] a = new Integer[n];
        Integer[] b = new Integer[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());
        }

        Arrays.sort(a);
        Arrays.sort(b, Collections.reverseOrder());

        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += a[i]*b[i];
        }

        System.out.println(sum);
    }
}