[백준] 1026. 보물

문제 링크

[백준] 1026. 보물

풀이 과정

문제에서 주어진 함수 S 의 값을 최소화하기 위해서는 매 순간 남아있는 수들 중 최대값과 최소값을 선택해 서로 곱해주어야 합니다.

배열 A의 최소값 0과 B의 최대값 8을 곱해 S에 누적시켜줍니다.

위 작업에서 제외된 후 배열 A의 최소값 1을 B의 최대값 7과 곱해 누적해줍니다.

이런 방식으로 마지막까지 진행해주면 S의 값이 최소가 됩니다.

문제에 배열 B를 재배열하면 안된다고 명시되어 있지만, 결국 배열 A는 오름차순으로, B는 내림차순으로 정렬한 후 인덱스 별로 요소를 곱해주어 누적시키면 정답이 됩니다.

코드

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

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 = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Integer[] B = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).boxed().toArray(Integer[]::new);
        int answer = 0;

        Arrays.sort(A);
        Arrays.sort(B, Collections.reverseOrder());

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

        System.out.println(answer);
    }
}