백준 알고리즘 1026번 풀이 - 보물

배열1[0] * 배열2[0] + ... + 배열1[N-1] * 배열2[N-1]의 값이 낮게 나오도록 B배열은 재배열 하지 말고 A배열만 재배열 하라고 한다.

그래서 쓸데없이 temp배열을 만들어서 풀었었는데, 생각해보니 정답만 잘 나오면 되는게 아닌가싶어 수정했다...

 

A배열과 B배열 중 하나는 오름차순 하나는 내림차순으로 정렬을 하여 곱한값을 더하면 S의 최솟값이 나온다.

 

소스

import java.util.Scanner;

public class Main {
	public static void main(String args[]){
		
		Scanner s = new Scanner(System.in);
		
		int n=s.nextInt();
		int tmp;
		
		int[] arr1 = new int[n];
		int[] arr2 = new int[n];
		int r=0;
		boolean flag = true;
		
		for(int i=0;i<n;i++) arr1[i] = s.nextInt();
		for(int i=0;i<n;i++) arr2[i] = s.nextInt();
		
		for(int i=0;i<n-1;i++){		//arr1 정렬
			flag=true;
			for(int j=1;j<n-i;j++){
				if (arr1[j] < arr1[j-1]){	
					tmp = arr1[j];
					arr1[j] = arr1[j-1];
					arr1[j-1] = tmp;
					flag=false;
				}
			}
			if (flag) break;
		}
		
		for(int i=0;i<n-1;i++){		//arr2 정렬
			flag=true;
			for(int j=1;j<n-i;j++){
				if (arr2[j] > arr2[j-1]){	
					tmp = arr2[j];
					arr2[j] = arr2[j-1];
					arr2[j-1] = tmp;
					
					flag=false;
				}
			}
			if (flag) break;
		}
		
		for(int a=0;a<n;a++){	//정답 계산
			r += arr1[a]*arr2[a];
		}
		System.out.println(r);
	}
}

나는 간단하게 버블정렬을 이용하여 풀었다.

배열1은 배열2는 내림차순으로 정렬하여 곱한값을 출력해주면 끝난다.