[BOJ - JAVA] 1026 - 보물(그리디 알고리즘)

# 주소

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

1026번: 보물

# 문제

# 문제 해설 및 코드 리뷰

import java.util.Arrays;
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		
		int[] arr = new int[n];
		int[] ans = new int[n];
		
		for(int i = 0; i < n; i++)
			arr[i] = scan.nextInt();
		for(int i = 0; i < n; i++)
			ans[i] = scan.nextInt();
		Arrays.sort(arr);
		int[] dp = new int[n];
		Arrays.sort(ans);
		for(int i = n-1; i >= 0; i--) {
			dp[n-1-i] = ans[i];
		}
		int sum = 0;
		for(int i = 0; i < n; i++) {
			sum += arr[i] * dp[i];
		}
		System.out.println(sum);
    }
}

이 문제의 핵심은 최소값을 만들기 위해 sum값이 어떻게 될지 유추해야 하는 문제입니다.

따라서 arr와 ans를 하나는 오름차순, 하나는 내림차순으로 정렬해야 합니다.

그러므로 각각 정렬하고 arr와 dp에 정렬된 ans를 역으로 저장하면 dp는 내림차순이 됩니다.

그리고 가가 index값에 따라 sum에 곱하여 넣고 더하면 최종적으로 최소값의 sum을 구할 수 있겠습니다.

너무 간단하죠???

감사합니다.