[BOJ]1026 - 보물 [C++]

안녕하세요. 오늘은 BOJ 1026번 보물을 풀어보겠습니다.

그리디 알고리즘으로 분류되어 있는 문제입니다.

배열 두개에 N개의 수열을 입력받고 A * B의 총합을 구하는데, 그 총합이 최소가 되게해야하는 문제입니다.

두 수열을 곱한 값의 총합이 최소가 되려면 두 수열중 큰 값은 작은 값과 곱해져야만 최소를 만들 수 있습니다.

 

예제를 들어 설명하면,

두 수열 A,B를 모두 정렬하면,

A : 0, 1, 1, 1, 6

B : 1, 2, 3, 7, 8

한 뒤에 배열 한 개를 역순으로 뒤집어서 계산해줬습니다.

 

S = A[0] * B[4] + A[1] * B[3] + ... + A[4] *B[0]

이렇게 계산해주면 예제처럼 합이 18이 나오게 됩니다.

 

코드를 보겠습니다.

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main() {
	int n = 0, sum = 0, cnt = 0;
	
	cin >> n;

	cnt = n;
	vector<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.begin(), A.end());
	sort(B.begin(), B.end());

	for (int i = 0; i < n; ++i) {
		for (int j = cnt - 1; j >= 0; --j) {
			sum += A[j] * B[i];
			--cnt;
			break;
		}
	}
	cout << sum;
}

감사합니다.