[Java] 백준 1026번 보물

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

1026번: 보물

문제 설명

• 길이가 N인 배열 A, B
• S = A [0]*B [0] +... + A [N-1]*B [N-1]
• 배열 A를 재배열해서 S를 최솟값으로 만들기. (단, B의 수는 재배열하면 안 됨)
• S의 최솟값 출력하기

 

우선 코드를 생각하지 않고 이론적으로 생각해보면 쉽게 풀린다.

S는 배열 A, B의 원소를 각각 곱한 합이기 때문에 최솟값을 구하기 위해 S = 가장 큰 값 * 가장 작은 값 + 두 번째로 큰 값*두 번째로 작은 값... 가장 작은 값 * 가장 큰 값 의 계산을 진행해주면 된다.

문제에서 B의 수는 정렬하면 안 된다고 나와있지만 S의 최솟값을 계산하여 출력하는 프로그램이기 때문에 내부적으로 정렬하여 풀어도 상관없다.

즉, 배열 A를 오름차순 정렬하고 배열 B를 내림차순 정렬하여 각 원소끼리 곱하여 더해주면 된다.

 

나는 배열 A,B을 둘 다 오름차순 정렬하여 for문 안에서 A의 첫 번째 값과 B의 마지막 값을 곱하여 S를 계산도록 하였다.

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String [] args) {
		Scanner s= new Scanner(System.in);
	
		int N = s.nextInt();
		int A[] = new int[N];
		int B[] = new int[N];
		int S=0;
		
		
		for(int i=0;i<N;i++) 
			A[i]=s.nextInt();
		
		for(int i=0;i<N;i++) 
			B[i]=s.nextInt();
		
		Arrays.sort(A);
		Arrays.sort(B);
		
		for(int i=0;i<N;i++) 
			S += A[i]*B[N-1-i];
		
		System.out.print(S);
		
	}
}