백준 1026 : 보물

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

1. 접근

• 원래대로라면 간단하게 a 배열과 b 배열을 각각 오름차순, 내림차순 정렬해서 큰수는 큰수끼리, 작은수는 작은수끼리 곱해주면 되는 문제였다
• 그러나, b 배열을 재배열하면 안된다는 조건으로 인해 난이도가 상승했다.
• a 배열의 가장 작은 수와 b 배열의 가장 큰 수를 곱해야한다는 의미는 동일하다.
  => b 배열의 가장 큰수만 찾아주면된다.
• 이미 큰 수로 선택되어 곱해졌던 수들은 bool 배열 isChoosen에서 true 처리를 해주었다.
  => false라면 큰 수로 선택할 수 있다.
• a 배열을 오름차순 정렬한 후, 가장 작은수부터, isChoosen이 false인 값들 중 가장 큰수를 찾아주는 과정을 반복문으로 구현하면 되는 문제였다.

2. 나의 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool cmp(int x, int y) {
	if (x >=y)	return true;
	else return false;
}

int main() {
	vector<int> a, b;
	int n;
	cin >> n;

	int s = 0;
	int tem = 0 ;
	for (int i = 0; i < n; i++) {
		cin >> tem;
		a.push_back(tem);
	}
	for (int i = 0; i < n; i++) {
		cin >> tem;
		b.push_back(tem);
	}

	sort(a.begin(), a.end());
	bool IsChoosen[100] = {false,};
	for (int i = 0; i < n; i++) {
		int maxindex = i;
		for (int j = 0; j < n; j++) {
			if (IsChoosen[maxindex] || (!IsChoosen[j]&&b[maxindex] < b[j])) {
				maxindex = j;
				//cout << maxindex << "\n";
			}
		}
		s += a[i] * b[maxindex];
		IsChoosen[maxindex] = true;
		//cout << a[i] << " X " << b[maxindex] << "\n";
	}
	
	cout << s << "\n";

}