백준 - 나무 자르기 ( 14247번, JAVA )

Greedy ( https://www.acmicpc.net/problem/14247 )

풀이

• 성장속도가 느린순으로 나무를 자르면 결국 성장속도가 빠른 나무는 day의 곱이 될테니 누적이 최대가됨
• 성장속도가 느린순으로 나무를 잘라주면서 answer에 day에 따른 성장한 나무길이를 누적하면 정답 ✈️

package problem_solving.greedy;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class BaekJoon_14247 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = Integer.parseInt(sc.next());
		
		int [][] arr = new int [n][2];
		
		for(int i = 0 ; i < 2;i++) {
			for(int j = 0 ; j  < n; j++) {
				arr[j][i] = Integer.parseInt(sc.next());
			}
		}
		Arrays.sort(arr,new Comparator<int[]>() {
			@Override
			public int compare(int [] o1, int [] o2 ) {
				return o1[1]-o2[1];
			}
		});
		int day = 0 ; 
		long answer = (long) 0 ;
		int index = 0 ; 
		while(n -- > 0 ) {
			answer+=arr[index][0]+(arr[index][1] * day);
			index++;
			day++;
		}
		System.out.println(answer);
	}

}