[백준_1026번] 보물

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

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보다 작거나 같은 음이 아닌 정수이다.

 

[코드]

import java.util.*;

public class BaekJoon_1026 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		Integer[] a=new Integer[n];
		int[] b=new int[n];
		int sum=0;
		
		for(int i=0;i<n;i++)
			a[i]=sc.nextInt();
		
		for(int i=0;i<n;i++)
			b[i]=sc.nextInt();
		
		// a 배열은 내림차순으로, b 배열은 오름차순으로 정렬 
		Arrays.sort(a,Collections.reverseOrder());
		Arrays.sort(b);
		
		// 두 배열을 곱한 값을 누적
		for(int i=0;i<n;i++)
			sum+=a[i]*b[i];
		
		System.out.println(sum);
	}
}

 

[고찰]

 이번 문제는 B 배열은 정렬하면 안된다라는 문장 때문에 고민을 좀 했던 문제였다. 처음에는 처음에는 B 배열을 정렬하지 않고 숫자의 크기 순을 저장하는 다른 배열을 선언해야 하나 고민했지만 B 배열도 정렬해서 풀어도 가능한 문제였다. A[0]×B[0] + ... + A[N-1]×B[N-1]의 값이 가장 작은 값을 찾는 것이기 때문에 B 배열은 오름차순으로, A 배열은 내림차순으로 정렬하여 두 배열의 값을 곱하는 것이 많은 경우의 수 중 가장 작은 값으 도출해내는 경우이기 때문에 위의 코드와 같이 풀면 정답 처리를 받을 수 있는 문제였다.