본문 바로가기
백준/자바

백준 자바 14247 나무 자르기

by 쎄오SseO 2022. 5. 10.

로직은 간단합니다.

초기 나무 길이가 4이고 자라는 길이가 6일 때

만약 5일 후에 자른다면 4 + 6 * 4 로 28이고 5일 후에 다시 자른다면 30만큼을 자르게 되어 총 58만큼 자르게 됩니다.

중간에 자르지 않고 10일 후에 자르게 된다면? 4 + 6 * 9로 똑같이 58만큼 자르게 됩니다.

그러면 굳이 자라는 길이가 제일 긴 나무를 처음에 자를 필요가 없게 됩니다.

자라는 길이가 제일 적은 것부터 자르게 되면 되는 것입니다.

저는 자라는 길이를 정렬해주는 것을 class를 이용하여 정렬 시켜주어봤습니다.

public class Baek14247 {

    public static class ATree{
        int Hi;
        int Ai;

    }

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        ATree[] arr = new ATree[n];


        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i < n; i++){
            arr[i] = new ATree();
            arr[i].Hi = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            arr[i].Ai = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr, new Comparator<ATree>() {
            @Override
            public int compare(ATree o1, ATree o2) {
                return o1.Ai - o2.Ai;
            }
        });

        long count = 0;

        for(int i = 0; i < n; i++){
            count = count + arr[i].Hi + i * arr[i].Ai;
        }

        System.out.println(count);
        br.close();
    }
}