[백준 1026] 보물 (Java) - 정렬, 그리디

https://www.acmicpc.net/problem/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의 최솟값을 출력한다.

예제 입력 1 복사

5
1 1 1 6 0
2 7 8 3 1

예제 출력 1 복사

18

---

풀이

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

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());
        int[] A = new int[N];
        int[] B = new int[N];

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

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

        // A 오름차순 정렬
        Arrays.sort(A);

        // B 내림차순 정렬
        B = IntStream.of(B)
                .boxed()
                .sorted((a,b) -> b - a)
                .mapToInt(Integer::intValue)
                .toArray();

        int sum = 0;
        for(int i=0; i<N; i++){
            sum += (A[i] * B[i]);
        }

        System.out.println(sum);
    }
}

• 정렬, 그리디를 활용한 문제
• S = A[0] × B[0] + ... + A[N-1] × B[N-1] 를 최소값으로 만드는 문제
• A, B배열의 같은 index요소끼리 곱해야 하기 때문에 정렬순서가 중요하다.
• S값을 최소로 만들어주려면 (큰수)x(작은수) 곱하는 조합으로 정렬해야 한다.
• 즉, A 배열은 오름차순, B배열은 내림차순 으로 정렬해서 곱해주면 된다.
• 내림차순의 경우, stream을 사용해서 내림차순 정렬해주었다.
• 정렬 해준 수, S를 구하기 위한 연산을 수행해주고 sum을 출력하면 된다.