백준 1026번 : 보물

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

벡터를 사용하는게 다 좋은 것은 아니라는 걸 오늘 다시 깨닫는다. 인덱스로 값 insert하려면 iterator을 사용해야 한다는 점이 꽤 큰 penalty로 다가온다.

이거 근데 할 말이 있다. 이 문제에 대해 높은 정답 비율을 보이는데 사실 들어가서 맞은 코드 살펴보면 B 배열 순서 조건을 어긴 코드가 태반이다. 그렇게 하면 나도 빨리 끝내고 다음 코드로 넘어갔지..

결론은 못풀었다. 우선은 벡터로 접근했다.

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

bool compare(int i, int j) { if (i > j) return true; return false; }

int main() {
	int num, elem;
	cin >> num;
	vector<int> b, a;
	vector<int> tmp_a, tmp_b;

	for (int i = 0; i < num; i++) {
		cin >> elem;
		tmp_a.push_back(elem);
	}
	for (int j = 0; j < num; j++) {
		cin >> elem;
		b.push_back(elem);
		tmp_b.push_back(elem);
	}

	sort(tmp_a.begin(), tmp_a.end(), compare);
	sort(tmp_b.begin(), tmp_b.end());

	int arr[50];
	for (int i = 0; i < num; i++) {
		int key = -1;
		for (int j = 0; j < num; j++) {
			if (tmp_b[i] == b[j])
				key = j;
		}
		arr[key] = tmp_a[i];
	}
	for (int i = 0; i < num; i++) {
		a.push_back(arr[i]);
	}

	int sum = 0;

	for (int i = 0; i < num; i++) {
		sum += (a[i] * b[i]);
	}

	cout << sum;
	return 0;
}

답은 나오는데 컴파일러가 틀렸다고 한다. tmp_a에서 a로 값을 옮기기 위해 배열을 써서 최대한 인덱스로 접근하는 행동을 하지 않았음에도 불구하고 틀렸다.

그래서 아예 배열로 접근해봤다.

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

bool compare(int i, int j) { if (i > j) return true; return false; }

void asort(int* a, int num) {
	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++) {
			if (a[i] > a[j]) {
				int temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
	}
}

int main() {
	int num, elem;
	cin >> num;
	int b[50], a[50], c[50], d[50];

	for (int i = 0; i < num; i++) {
		cin >> elem;
		d[i] = elem;
	}
	for (int j = 0; j < num; j++) {
		cin >> elem;
		b[j] = elem;
		c[j] = elem;
	}

	asort(d, num);
	asort(c, num);
	for (int i = 0; i < num; i++) {
		int key = -1;
		for (int j = 0; j < num; j++) {
			if (c[i] == b[j]) {
				key = j;
				a[key] = d[num-i-1];
			}
		}
	}

	int sum = 0;

	for (int i = 0; i < num; i++) {
		sum += (a[i] * b[i]);
	}

	cout << sum;
	return 0;
}

틀렸다.

중복된 요소를 처리를 못하는건지 아니면 어디에서 구멍이 난 것인지 모르겠다. 나중에 풀어보자.