백준 1026

백준 1026번 문제 : 보물

간단한 문제고, 정렬을 이용하면 된다.

간단하게 푸려면 a는 오름차순, b는 내림차순으로 정렬해서 풀면 되지만 그렇게 되면 문제의 출제의도에 어긋난다고 생각한다.
실제로 인터넷을 찾아보니 답이 나온다는 이유로 b 배열도 정렬해서 푸는 경우가 대부분이었다.

우선순위 큐 (priority queue)를 이용하는 방법도 있지만, 이 또한 b를 정렬해 푸는 것과 다름이 없었다.

따라서 시간은 더 걸렸지만, b를 정렬하지 않고 문제를 풀었다.

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n;
	
	cin>>n;
	
	
	int a[n], b[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); //a를 오름차순으로 정렬
	
	
	int check[n], index[n];
	for(int i=0; i<n; i++) {
		check[i] = 0;
	}
	
	for(int i=0; i<n; i++) {
		int max = 0;
		int maxIndex = 0;
		
		for(int j=0; j<n; j++) {
			if(check[j]==0 && b[j]>=max) {
				max=b[j];
				maxIndex=j;
			}	
		}
		
		check[maxIndex]=1;
		index[i] = maxIndex;
	}
	
	int sum=0;
	
	for(int i=0; i<n; i++) {
		sum += a[i]*b[index[i]];
	}
	
	cout<<sum<<"\n";
	
	
	return 0;
}

b 배열을 돌면서 최대값 순서대로 인덱스들을 index 배열에 저장했다가, 곱셈을 할 때 최대인 인덱스 순으로 찾아들어가도록 풀이하였다.

b까지 정렬하면 O(N)으로 풀리겠지만 이렇게 풀면 O(N^2)이 걸린다.