[실버4] BOJ1026 보물

문제 분석

• 기본식 → S = A[0] × B[0] + ... + A[N-1] × B[N-1]
• S에서 A 배열의 요소만 재배열 가능하다
• S의 최솟값을 구하시오.

손으로 풀기

1. A를 오름차순으로 정렬한다.
2. B를 오름차순으로 정렬한다.
3. N번 반복하면서 A는 오름차순으로, B는 내림차순으로 조회되는 요소를 곱한다.
4. 3번이 반복될떄마다 나온 결과값을 배열에 넣는다.
5. 반복문이 종료되면 배열의 모든 요소를 더한 값을 출력한다.

Sudo code

함수 최소_합계_계산(N, 배열 A, 배열 B):
    A_정렬됨 = A를 오름차순으로 정렬
    
	B_정렬됨 = B를 오름차순으로 정렬    
	
 	int[] result = 결과를 담을 배열
    
    for(0부터 N-1까지) :
    result배열.add(A정렬[i] * B정렬[N-i-1])

	totalSum = result배열 모든 요소 합친 값
	
    출력(totalSum)

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

//TIP 코드를 <b>실행</b>하려면 <shortcut actionId="Run"/>을(를) 누르거나
// 에디터 여백에 있는 <icon src="AllIcons.Actions.Execute"/> 아이콘을 클릭하세요.
public class BOJ1026 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] arrayA = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        int[] arrayB = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        List<Integer> resultList = new ArrayList<>();

        if(arrayA.length > 0) Arrays.sort(arrayA); // NlogN
        if(arrayB.length > 0) Arrays.sort(arrayB); // NlogN

        for(int i=0;i<N;i++){
            resultList.add(arrayA[i] * arrayB[N-i-1]);
        }

        int totalSum = resultList.stream()
                .mapToInt(Integer::intValue) // 또는 .mapToInt(i -> i)
                .sum();

        System.out.println(totalSum);
    }
}