[C++] 백준 1026번: 보물

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

1026번: 보물

아이디어

큰 수와 작은수를 짝지어 곱하면 총 합은 작아진다.

 

풀이

배열 A는 vector<int> 형식에 담고, B는 vector<pair<int, int>> 형식에 fisrt에는 값을, second에는 인덱스를 담았다. B를 copied라는 벡터에 복사하고 A는 내림차순, copied는 first 기준 오름차순으로 정렬했다. copied의 fisrt 값을 A의 값으로 순서대로 대체하고 copied의 second 기준으로 오름차순 정렬을 했다. 그런 다음, 순서대로 copied의 fisrt 값과 B의 first값을 곱하고 더해나가면 답이 나온다.

 

코드

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define EL "\n"

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int N;
	cin >> N;

	vector<int> A(N);
	vector<pair<int, int>> B(N);
	FOR(i, N)
		cin >> A[i];
	
	FOR(i, N) {
		cin >> B[i].first;
		B[i].second = i;
	}

	auto copied = B;
	sort(copied.begin(), copied.end());
	sort(A.rbegin(), A.rend());

	FOR(i, N)
		copied[i].first = A[i];
	sort(copied.begin(), copied.end(),
		[](pair<int, int> lhs, pair<int, int> rhs) {
			return lhs.second < rhs.second;
		});

	int result = 0;
	FOR(i, N)
		result += copied[i].first * B[i].first;
	cout << result << EL;


	return 0;
}