[JAVA] 백준 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 ( 50보가 작거나 같은 자연수)

- 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어짐 ( 100보다 작거나 같은 음이 아닌 정수)

- 셋째 줄에는 B에 있는 수가 순서대로 주어짐 ( 100보다 작거나 같은 음이 아닌 정수)

 

출력

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

 

풀이

S의 값이 가장 작게 만들기 위해서는 (A에서 가장 작은 수)와 (B에서 가장 큰 수), (A에서 가장 큰수)와 (B에서 가장 작은 수) 같은 식으로 곱해지게 만드는 것이다.

즉, 배열 A와 B를 반대로(하나는 오름차순, 나머지 하나는 내림차순) 정렬했을 때가 S의 최솟값이다.

하지만 이때 B에 있는 수는 재배열하면 안되므로 B의 값을 따로 받아 정렬한다.

 

배열을 정렬하기 위해서 java.util.Arrays 유틸리티 클래스의 sort() 메서드를 사용했다.

sort() 메서드의 기본 정렬조건은 오름차순이다.

 

내림차순을 하기 위해서 java.util.Collection 클래스의 reverseOrder() 메서드를 사용했다.

이는 지금까지와 반대 오더, 즉 반대로 소트하겠다는 의미로 내림차순 적용이 가능이다.

이때 주의할 점은 Primitive Type(byte, char, double, short, long int, float) 의 배열에는 적용이 불가능해 Integer같은 Wrapper 클래스를 이용해야한다는 것이다.

 

public class bj1026 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner s = new Scanner(System.in);
		
		int n = s.nextInt();
		
		int A[] = new int[n];
		for(int i=0;i<n;i++)
			A[i] = s.nextInt();
		
		int B[] = new int[n];
		for(int i=0;i<n;i++)
			B[i] = s.nextInt();		
		
		Integer temp[] = new Integer[n];
		for(int i=0;i<n;i++)
			temp[i] = B[i];		
		
		Arrays.sort(A);
		Arrays.sort(temp,Collections.reverseOrder()); // 내림차순정렬
		
		int S=0;
		for(int i=0;i<n;i++)
			S += A[i]*temp[i];
		
		System.out.println(S);
	}

}