[백준 1026] - 보물

문제

• 옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.
• 길이가 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의 최솟값을 출력한다.

 

솔루션

• 동일한 인덱스에 위치한 A, B 배열의 값을 서로 곱해 모두 합친 값이 S가 될 것이다.
• 이 S를 최소로 하기 위해서는 A 배열은 큰 수부터, B 배열은 작은 수부터 시작하여 서로 곱하면 된다.
• 문제에서 B 배열은 재배열 하면 안된다고 나와있지만 결과적으로 S의 값만 출력하면 되기 때문에 A, B 둘 모두 정렬한 뒤, 곱해주면 될 것이다.

 

Code

import java.util.*;
import java.io.*;
 
public class Solution_1026 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        int n = Integer.parseInt(br.readLine());
 
        int[] alist = new int[n];
        int[] blist = new int[n];
 
        st = new StringTokenizer(br.readLine());
 
        for (int i = 0; i < n; i++)
            alist[i] = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
 
        for (int i = 0; i < n; i++)
            blist[i] = Integer.parseInt(st.nextToken());
 
        Arrays.sort(alist);
        Arrays.sort(blist);
 
        int result = 0;
 
        for (int i = 0; i < n; i++)
            result += alist[i] * blist[n - i - 1];
        
        bw.write(result + " ");
        
        bw.flush();
        bw.close();
        br.close();
    }
}
 

 

결과

5
1 1 1 6 0
2 7 8 3 1
18