프로그래밍/백준알고리즘
백준 알고리즘 1026번 풀이 - 보물
밍구몬
2019. 9. 25. 17:37
배열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는 내림차순으로 정렬하여 곱한값을 출력해주면 끝난다.