[백준] 1026번: 보물 [C++]

 

알고리즘 분류: 수학, 그리디 알고리즘, 정렬

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

1026번: 보물

 

 

 

 

【 풀이 】

 

A 배열을 정렬하고 B 배열을 정렬하지 않았을 때, 각 요소들을 곱해서 더한 값이 최솟값이 되게 하는 문제이다.

이 문제는 A 배열에서의 최댓값 * B 배열에서의 최솟값을 각각 더해가면 간단하게 해결할 수 있다.

 

그러나 이 문제는 B 배열을 정렬했다고 해서 큰 문제는 없다.

문제 의도에 맞지 않지만, 그렇다고 해서 더 좋은 풀이를 사용하지 않을 이유는 없기에 B 배열도 정렬하여 풀었다.

 

즉 algorithm 헤더의 sort 함수를 사용해서 A 배열은 내림차순으로, B 배열은 오름차순으로 정렬하면 쉽게 해결할 수 있다.

 

 

 

【 코드 】

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

int N;
int A[51];
int B[51];

int main() {
	int result = 0;

	cin >> 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, greater<int>());	// 내림차순
	sort(B, B + N, less<int>());	// 오름차순

	for (int i = 0; i < N; i++) {
		int temp = 1;
		temp = A[i] * B[i];
		result += temp;
	}

	cout << result;

	return 0;
}