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

 

그리디 문제입니다. 나무가 자라는 길이가 작은 순으로 자르면 됩니다. 길게 자라는 나무를 최대한 나중에 잘라야 최대치로 구할 수 있겠죠

그럼 결국 첫번째줄의 숫자는 다 더하고, 두번째 줄의 숫자를 정렬한 다음 sum += a[i]*i를 해주면 최대값입니다.

 

#include <bits/stdc++.h>
using namespace std;


typedef long long ll;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n;
	cin >> n;

	ll sum = 0;
	for (int i = 0; i < n; ++i) {
		int in;
		cin >> in;
		sum += in;
	}

	vector<int> growing(n);
	for (auto& c : growing)
		cin >> c;

	sort(growing.begin(), growing.end());
	for (int i = 0; i < n; ++i)
		sum += growing[i] * i;

	cout << sum << '\n';

	return 0;
}
반응형