[BOJ][14247] 나무 자르기 - JAVA

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

14247번: 나무 자르기

 

- 풀이

 - 탐욕법 문제

 - 현재 최선의 방법을 구하는 문제 

 - 성장 가능성만 따져서 성장 가능성이 가장 낮은 것 부터 잘라낸다

 

 

import java.util.*;

public class Solution {
    static class Tree {
        int baseNum;
        int growNum;

        public Tree(int baseNum, int growNum) {
            this.baseNum = baseNum;
            this.growNum = growNum;
        }
    }

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        long answer = 0;
        int n = sc.nextInt();
        int[] Hi = new int[n];
        int[] Ai = new int[n];
        PriorityQueue<Tree> pq = new PriorityQueue<Tree>((a, b) -> a.growNum - b.growNum);
        for (int i = 0; i < n; i++) {
            Hi[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            Ai[i] = sc.nextInt();
        }

        for (int i = 0; i < n; i++) {
            pq.add(new Tree(Hi[i], Ai[i]));
        }

        int growCount = 0;

        while (!pq.isEmpty()) {
            Tree ct = pq.poll();
            int treeHeight = ct.baseNum + (ct.growNum * growCount++);
            answer += treeHeight;
        }

        System.out.println(answer);
    }
}