[BOJ] 1026 보물

Link https://www.acmicpc.net/problem/1026

Note

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;
}

2019-01-12 12:00:00에 Tistory에서 작성되었습니다.