백준 알고리즘 - 1026번 : 보물

백준 알고리즘 1026번 보물문제 입니다.

(참고 - https://www.acmicpc.net/problem/1026 )

코드)

#include <stdio.h>

int main() {

int i, j, testcase, temp, S=0;

int arr_A[101];

int arr_B[101];

scanf("%d", &testcase);

for(i=0; i<testcase; i++) {

scanf("%d", &arr_A[i]);

}

for(i=0; i<testcase; i++) {

scanf("%d", &arr_B[i]);

}

for(i=0; i<testcase; i++) {

for(j=0; j<i; j++) {

if(arr_A[j] < arr_A[i]) {

temp = arr_A[i];

arr_A[i] = arr_A[j];

arr_A[j] = temp;

}

}

}

for(i=0; i<testcase; i++) {

for(j=0; j<i; j++) {

if(arr_B[j] > arr_B[i]) {

temp = arr_B[i];

arr_B[i] = arr_B[j];

arr_B[j] = temp;

}

}

}

for(i=0; i<testcase; i++)

S += arr_A[i] * arr_B[i];

printf("%d\n", S);

return 0;

}

- 먼저 말씀드리면, 해당 문제에서 함정이 하나 있습니다. 

바로   단, B에 있는 수는 재배열하면 안된다. 라는 글귀입니다.

물론 재배열 하지 않고 쉽게 할 수있는 방법을 빠르게 찾을 수 있다면, 그 방법이 가장 좋을 것같습니다..^^

다만 제 생각은 결론적으로 S의 값을 가장 작게 만들어 주기 위하여 A배열과 B배열의 값을 곱해주게 될 때, 

A배열의 값이 변함에 따라서 B배열 또한 결과적으로 변하게 됩니다.

따라서 A배열과 B배열을 먼저 재배열하여 곱해주어 S의 최솟값을 구해도 상관이 없다는 점입니다.

(* S의 최솟값을 구하기 위해서는 'A배열의 가장 큰 수 * B배열의 가장 작은 수' 를 해주어야하고, 따라서 A배열의 인덱스가 낮은 순으로 큰 값으로 정렬을 하거나, 작은 값으로 정렬하게 되면, B배열은 A배열에 대해 반대로 정렬 해주어야 한다는 뜻입니다.)

즉, arr_A, arr_B 배열을 생성하여 값을 입력받게 한 뒤, 단순 버블소트(bubble sort)를 이용하여 A와 B 둘 다 정렬을 해줍니다. (저는 단순히 버블소트를 사용하였지만 다른 효율적인 정렬 알고리즘을 사용하시는 것이 좋습니다..라고 생각합니다.)

그 후 정렬된 A,B 배열을 이용하여 S 값을 구해주면 최소 S를 구할 수 있습니다.

+Java)

import java.util.Arrays;

import java.util.Scanner;

public class algo1026 {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int loop = sc.nextInt();

int[] arrA = new int[loop];

int[] arrB = new int[loop];

int[] tmp = new int[loop];

for(int i=0; i<loop; i++)

arrA[i] = sc.nextInt();

for(int i=0; i<loop; i++)

arrB[i] = sc.nextInt();

Arrays.sort(arrA);

Arrays.sort(arrB);

int j=0;

for(int i=arrB.length-1; i>=0; i--)

tmp[j++] = arrB[i];

int minresult=0;

for(int i=0; i<loop; i++)

minresult += arrA[i] * tmp[i];

System.out.println(minresult);

sc.close();

}

}