[14247] 나무 자르기

🔗 문제 링크

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

🔍 문제 설명

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

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

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

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

⚠️ 제한사항

•  $1≤n≤100\,000$ 

• $1≤H_i≤100\,000$ 

• $1≤A_i≤10\,000$ 

---

🗝 풀이 (언어 : Java)

가장 자라는 폭이 큰 나무를 제일 마지막에 자르는 것이 가장 많은 나무를 얻는 방법이다.
자라는 길이 순으로 정렬해서 자라는 길이가 작은 순으로 자르도록 구현했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
		StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
		br.close();
		int[][] trees = new int[n][2];
		for (int i = 0; i < n; i++) {
			trees[i][0] = Integer.parseInt(st1.nextToken()); //현재 길이
			trees[i][1] = Integer.parseInt(st2.nextToken()); //매일 자라는 길이
		}
		solution(trees);
	}

	private static void solution(int[][] trees) {
		//매일 자라는 길이순 정렬(마지막은 가장 증가 폭이 큰 나무)
		Arrays.sort(trees, (o1, o2) -> o1[1] - o2[1]);
		long sum = 0; //합계는 int 범위를 넘으므로, long 자료형
		for (int i = 0; i < trees.length; i++) {
			sum += trees[i][0] + (i * trees[i][1]); //매일 자르는 나무 합산(최대 값 = 20억 -> int 자료형 가능)
		}
		System.out.println(sum);
	}

}