문제 요약

[1026] 보물

S를 작게 만들기 위하여 배열 A를 재배열한다. (단, B에 있는 수는 재배열 하면 안 된다)

풀이 과정

배열 B의 값 중에서 가장 큰 값은 배열 A의 값 중에 가장 작은 값과 매칭하여 곱해주면 된다.
문제에서 B는 재배열하지 말라고 했는데, A와 B모두 오름차순으로 정렬한 다음에 배열을 탐색할 때 A는 인덱스 0번부터 (작은 순으로) B는 인덱스 맨 끝부터 (큰 순으로) 탐색하며 둘이 곱하고 그 값을 누적하여 더해주는 방식으로 진행함.

코드 (C/C++)

비교함수

• 1, 0, -1 중에 하나를 반환
• 오름차순으로 정렬한다면 (내림차순인 경우 등호 바꿔서)
  * 첫번째 변수 > 두번째 변수 => 1
  • 첫번째 변수 < 두번째 변수 => -1
  • 첫번째 변수 = 두번째 변수 => 0

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compare(const void* first, const void* second)
{
	if (*(int*)first > *(int*)second) return 1;
	else if (*(int*)first < *(int*)second) return -1;
	else return 0;
} //오름차순 정렬

int main(void)
{
	int n;
	int res = 0;
	int* a;
	int* b;
	scanf("%d", &n); 
	a = (int*)malloc(sizeof(int) * n);
	b = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &b[i]);
	}
	qsort(b, n, sizeof(int), compare); //오름차순
	qsort(a,  n, sizeof(int), compare); //오름차순
	for (int i = 0; i < n; i++)
	{
		res = res + (a[i] * b[n - 1- i]);
	}
	printf("%d", res);
}