[Baekjoon] 1026 - 보물

📝 문제

 

 

🔑 풀이 과정

· 우리가 구해야 하는 것 = S의 최솟값

S는 각 배열에서 원소를 하나씩 뽑은 후 곱해서 전부 더한 것이다.

S가 최소가 되려면 더해지는 각 항들도 가능한 한 최소가 되어야 한다.

A 배열 중 가장 작은값 * B 배열 중 제일 큰 값 + ... + A 배열중 제일 큰 값 * B 배열 중 제일 작은 값

이런 식으로 계산하면 최소가 된다.

 

· 문제에 B에 있는 수는 재배열 하면 안된다 되어있지만, 우리가 B가 재배열되지 않았을 때의 A 배열을 출력하는 것도 아니고, S의 최솟값을 구하는게 목적이기 때문에 정렬을 하든말든 아무 상관이 없다.

 

· 풀이 과정

 

 

 

🔓 답안

import java.io.*;
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        //입력
        int N = Integer.parseInt(br.readLine());

        int[] arrA = new int[N];
        int[] arrB = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            arrA[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            arrB[i] = Integer.parseInt(st.nextToken());
        }

        //정렬
        Arrays.sort(arrA);
        Arrays.sort(arrB);

        //계산
        int sum = 0;
        for(int i = 0; i < N; i++){
            sum += arrA[i] * arrB[N-1-i];
        }

        //출력
        bw.write(sum + "\n");
        bw.flush();
        bw.close();
    }

}

 

 

 

🖤 알고리즘 분류

- 수학

- 그리디 알고리즘

- 정렬