백준 1026 - 보물 (자바 - 그리디)

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

1026번: 보물

 

* 문제 요약

수학이 항상 큰 골칫거리였던 나라가 다음과 같은 문제를 내고 큰 상금을 걸었다.

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

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

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

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

 

* 입력

- 첫째 줄에 N 이 주어진다.

- 둘째 줄에는 A 에 있는 N 개의 수가 순서대로 주어지고

- 셋째 줄에는 B 에 있는 수가 순서대로 주어진다.

- N 은 50보다 작거나 같은 자연수이고, A 와 B의 각 원소는 100 보다 작거나 같은 음이 아닌 정수이다.

 

* 출력

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

 

* 예시

 

* 해결 과정

B 배열을 재배열하지 말라고 하는 조건이 있으나, 결국 최솟값에 최대한 가까운 값을 찾으려면 특정 배열의 최솟값 * 특정 배열의 최대값 형식으로 연산한 뒤 그 값들을 합산해야 한다.

문제의 조건과는 다르나 A 배열만 재배열해서 함수 S 를 최소화 시키는 경우와 같은 정답을 낼 수 있다면 그 또한 얼마든지 정답이 될 수 있는 것이다.

 

* 코드 첨부

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Collections;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int size = Integer.parseInt(br.readLine());
        Integer[] a = new Integer[size];
        Integer[] b = new Integer[size];

        String[] input = br.readLine().split(" ");
        for (int i = 0; i < input.length; i++) {
            a[i] = Integer.parseInt(input[i]);
        }

        input = br.readLine().split(" ");
        for (int i = 0; i < input.length; i++) {
            b[i] = Integer.parseInt(input[i]);
        }

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

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

        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

A 배열을 오름차순 정렬, B 배열을 내림차순 정렬한 뒤 매 반복마다 각 요소들을 곱해준 다음 그 값들을 합산하여 함수 S 의 최솟값을 구했다.

함수 S 의 최솟값을 구하기 위해 각 배열을 서로 다른 방식으로 정렬하면서 최적화 하였으므로 그리디 알고리즘 문제에 해당된다.