[백준 14247] 나무 자르기 (C++)

https://www.acmicpc.net/problem/14247

 

문제

---

영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 나무들이 밤만 되면 매우 빠른 속도로 자라는데, 그 자라는 길이는 나무마다 다르다.

따라서, 어느 나무를 먼저 잘라가느냐에 따라서 총 구할 수 있는 나무의 양이 다른데,

나무의 처음 길이와 하루에 자라는 양이 주어졌을 때, 영선이가 얻을 수 있는 최대 나무양을 구하시오.

참고로, 자른 이후에도 나무는 0부터 다시 자라기 때문에 같은 나무를 여러 번 자를 수는 있다.

 

입력

---

첫째 줄에는 나무의 개수 n개가 있다. 나무는 1번부터 n번까지 있다.

다음 줄에는 첫날 올라갔을 때 나무의 길이들 H_i가 n개가 순서대로 주어진다.

그 다음 줄에는 나무들이 자라는 길이 A_i가 n개가 순서대로 주어진다.

 

출력

---

영선이가 나무를 잘라서 구할 수 있는 최대 양을 출력하시오.

 

제한

---

•  1 ≤ n ≤ 100,000 
•  1 ≤ H_i ≤ 100,000
•  1 ≤ A_i ≤ 10,000

문제 풀이

---

그리디 문제.

나무를 최대한 길게 자를 수 있도록 하루에 자라는 나무의 높이가 작은 순서대로 잘라주면 된다. 하루에 자라는 나무의 높이 H를 기준으로 오름차순 정렬하여 앞에서부터 자른다. H * 지난 날짜 + 첫 날 나무의 높이가 해당 날짜에 얻을 수 있는 나무의 길이이다.

 

아래는 코드.

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

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	pair<int, int>* arr = new pair<int, int>[N];
	long long answer = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i].second;
	}
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i].first;
	}
	sort(arr, arr + N);
	for (int i = 0; i < N; i++)
	{
		answer += arr[i].first * i + arr[i].second;
	}
	cout << answer << "\n";
	return 0;
}