[성실코딩 25일차] 백준 #1026 보물 *

허무한 문제구먼,,, 

처음에는 A를 정렬할 수 있는 모든 경우를 다 구해서, 곱하고 최소만 저장하는 방식

으로 풀었는데 -> 시간초과

풀이법은

A를 오름차순으로 정렬, B를 내림차순으로 정렬

그리고 곱하면 최소 값이 나온다.....

틀린 코드 - 시간초과

#include < iostream >

#define INF 987654321

using namespace std;

int N;
int A[50];
int B[50];

int map[50][50];
int prev_visited[50];
int minimum = INF;

void func(int _r, int ans) {
	int visited[50] = { 0, };
	if (_r==N) {
		if (minimum > ans) {  // update
			minimum = ans;
		}
		return;
	}

	for (int k = 0; k < N; k++) {
		if (prev_visited[k]==0 && visited[k]==0) {
			prev_visited[k] = 1; // 다음 index를 위해서
			visited[k] = 1;
			ans += map[_r][k];

			if (ans < minimum) { // 현재 최소값보다 작을 때만 실행해주면 돼
				func(_r + 1, ans);
			}
			
			// 초기화
			ans -= map[_r][k];
			prev_visited[k] = 0;
		}
	}
}

int main() {

	// 입력
	cin >> N;
	for (int k = 0; k < N; k++) {
		cin >> A[k];
	}
	for (int k = 0; k < N; k++) {
		cin >> B[k];
	}

	// map 채우기
	for (int r = 0; r < N; r++) { // B
		for (int c = 0; c < N; c++) {  // A
			map[r][c] = A[c] * B[r];
		}
	}

	// 한 줄마다 값을 골라서 최소값 만들기
	func(0,0);

	cout << minimum << endl;
	return 0;
}

옳은 코드

#include < iostream >
#include < algorithm >
#include < functional > // greater 

using namespace std;

int N;
int A[50];
int B[50];

int main() {

	// 입력
	cin >> N;
	for (int k = 0; k < N; k++) {
		cin >> A[k];
	}
	for (int k = 0; k < N; k++) {
		cin >> B[k];
	}

	// A 오름차순으로 정렬
	sort(A,A+N);

	// B 내림차순으로 정렬 
	sort(B, B + N, greater< int >());
	
	// 곱하기
	int answ = 0;
	for (int i = 0; i < N; i++) {
		answ += A[i] * B[i];
	}


	cout << answ << endl;
	return 0;
}