[BOJ] 1026번 : 보물

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n; 
int a[55];
int b[55]; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n; 
	for (int i = 0; i < n; i++) cin >> a[i]; 
	for (int i = 0; i < n; i++) cin >> b[i]; 
	sort(a, a + n);
	sort(b, b + n, [](int& x, int& y) {
		return x > y;
		});
	int ans = 0;
	for (int i = 0; i < n; i++) {
		ans += a[i] * b[i];
	}
	cout << ans << '\n';
}

 

greedy 하게 들어갔다. a라는 수열을 오름차순으로, b라는 수열은 내림차순으로 정렬한 뒤, 곱했다. 

처음 든 생각은 최댓값에는 최솟값을 곱하고, 최솟값에는 최댓값을 곱하면 분산이 적어지면서, 최솟값이 나오지 않을까?라는 생각으로 접근했다.