(cpp) Baekjoon 1026번 문제 ‘보물’ - 그리디알고리즘

01 Oct 2022 on Programming Languages

Baekjoon 1026번 문제 ‘보물’ - 그리디알고리즘

---

문제

풀이

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
using namespace std;
int n;
int a[51];
int b[51];

bool compare(int i, int j)
{
	return i > j;
}
int main() {
	//길이 n
	//정수배열 a,b
	//s = a[0] * b[0] + a[1] * b[1] + ... + a[n-1] * b[n-1]
	//s를 가장 작게 만들 수 있도록 A를 재배열
	//b는 건들면 안됨
	//s의 최솟값?
	//--> 배열 b의 원소중 큰 값일수록 a의 원소중 작은 값이 곱해지도록 재배열
	//s만 구하면 되므로, b sort하고 계산해도 됨.

	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); //오름차순
	sort(b,b+n,compare); //내림차순
	int s = 0;
	for (int k = 0; k < n; k++) {
		s = s+ a[k] * b[k];
	}
	printf("%d", s);

}