무지개 달팽이

Q. 옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0]*B[0] + ... + A[N-1]*B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

입력.

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

출력.

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

( 배열 A의 요소 ) X ( 배열 B의 요소 ) 의 형태로 만들어 그 합의 최솟값을 구하는 문제이다. 

이 문제는 아래와 같은 두 가지 방식으로 접근했다.

※ 정렬은 버블정렬을 이용하였다.

①

문제에는 배열 B는 재배열 하지 않는다는 조건이 있지만, 단순히 문제를 해결하기 위해서는 다음과 같은 방법을 사용할 수 있다.

배열 B의 요소값은 큰 순서대로 배열 A의 요소값이 작은 순서대로 정렬

+

후에 곱하여 모두 더함

즉, 정렬 알고리즘만을 이용하여 해결한 경우이다.

#include <stdio.h>

#define swap(type, x, y) do{type t = x; x = y; y = t;} while(0)

void a_bubble (int a[], int n) {
	int i, j;

	for (i = 0; i < n - 1; i++)
		for (j = n - 1; j > i; j--)
			if (a[j - 1] > a[j])
				swap(int, a[j - 1], a[j]);
}

void b_bubble(int a[], int n) {
	int i, j;

	for (i = 0; i < n - 1; i++)
		for (j = n - 1; j > i; j--)
			if (a[j - 1] < a[j])
				swap(int, a[j - 1], a[j]);
}

int main(void) {
	int i, n, ans = 0;
	int a[50], b[50];

	scanf("%d", &n);
	
	for (i = 0; i < n; i++)
		scanf("%d", &a[i]);
	
	for (i = 0; i < n; i++)
		scanf("%d", &b[i]);

	a_bubble(a, n);
	b_bubble(b, n);
	
	while (n--) 
		ans += (a[n]*b[n]);

	printf("%d\n", ans);
	
	return 0;
}