백준 1026 풀이

링크텍스트

문제는 링크를 참고.
정말 간단한 문제였다.
두 배열의 요소를 각각 곱해서 더한 값이 최소가 되도록 하면 되는데 이는 결국 하나의 배열에서는 최소를 가져오고 다른 하나의 배열에서는 최대를 가져와 곱해서 더하면 끝나는 것이다.

이를 위해 처음에는 각각 배열에서 A에서는 최소를 찾고 B에서는 최대를 찾아 곱하려고 했는데 이는 너무 시간도 많이들고 효율적이지 못하다고 생각이 들어 다른 방법을 생각해보았다.

최대 최소를 찾아 재배열 하는 것이나 배열을 정렬하는 것이나 다른 것이 무엇일까?

이러한 의문에 힘입어 A,B를 정렬하기로 결정했다. 문제에서 B를 재배열하지 마라고 했지만 B를 C라는 다른 배열에 복사해서 C를 정렬하면 B를 재배열하지 않고 문제를 푼 것과 다름이 없기때문에 그냥 두 배열을 정렬했다.

A는 오름차순으로 정렬했고, B는 내림차순으로 정렬했다.

그리고 각 인덱스마다 곱해서 더해주면 끝이난다.

코드는 아래와 같다.

#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <cstdlib>
#include <algorithm>
using namespace std;

int main() {
	int n;
	cin >> n;

	vector<int> A, B;

	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		A.push_back(tmp);
	}

	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		B.push_back(tmp);
	}

	sort(A.begin(), A.end());
	sort(B.begin(), B.end(), greater<int>());

	int answer = 0;
	int maxB = -1;
	
	for (int i = 0; i < n; i++) {
		answer += A[i] * B[i];
	}
	
	cout << answer << '\n';
}