BaekJoon 1026 보물

Link https://www.acmicpc.net/problem/1026
소스결과 1988 KB / 0 ms

출처 Backjoon 

언어 C++ 17

분류 정렬

 

설명

S 의 값을 최소로 만들어야 하는 문제

위 공식을 통해 최소로 만들기 위해서는 a는 오름차순으로, b는 내림차순으로 정렬하면 된다.

 

문제에서는 재배열 하면 안된다고 쓰여 있지만 정답과는 관련이 없기에 정렬 해주자

 

알고리즘

1. a와 b를 입력 받는다.

2. a를 오름차순 정렬한다.

3. b를 내림 차순 정렬한다.

4. 각 위치의 값을 곱해 전부 더한다.

5. 출력

 

소스코드

#include <iostream>

using namespace std;

int main()
{
	int n;
	int a[50];
	int b[50];
	int sum = 0;

	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> a[i];

	for (int i = 0; i < n; i++)
		cin >> b[i];

	// Selection Sort
	for (int i = 0; i < n; i++)
	{
		int min = i;
		for (int j = i; j < n; j++)
			if (a[min] > a[j])
				min = j;
		swap(a[min], a[i]);
	}

	// Selection Sort
	for (int i = 0; i < n; i++)
	{
		int max = i;
		for (int j = i; j < n; j++)
			if (b[max] < b[j])
				max = j;
		swap(b[max], b[i]);
	}

	for (int i = 0; i < n; i++)
		sum += a[i] * b[i];
	cout << sum;

	return 0;
}