[BOJ 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$ 

[풀이 코드]

---

import java.io.*;
import java.util.*;

public class 나무자르기 {
	static class tree{
		int value, speed;
		tree(int value, int speed){
			this.value=value;
			this.speed=speed;
		}
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int[] arr2 = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr2[i] = Integer.parseInt(st.nextToken());
		}
		tree[] trees = new tree[N];
		for (int i = 0; i < N; i++) {
			trees[i] = new tree(arr[i], arr2[i]);
		}
		Arrays.sort(trees, (o1, o2) -> o1.speed - o2.speed);
		
		long result = 0;
		for (int i = 0; i < N; i++) {
			result+=trees[i].value+(trees[i].speed*i);
		}
		System.out.println(result);
	}
}

이 문제를 접했을 때 n이 1부터 10만까지여서 바이너리 서치로 풀어야 된다고 생각을 했다.
그런데 문제를 보니 나무를 자루는 순서만 잘 정하면 답이 바로 나오겠단 생각이 들었다.

그래서 i번째 날에 얻은 나무 길이는 H+A*i 로 했고 성장 속도가 큰 나무를 뒤에 자르면 자라는 시간이 길어져서 이득이여서 성장 속도가 작은 나무부터 잘라야 하기 때문에 성장 속도를 기준으로 오름차순 정렬을 했다.