14247번. 나무 자르기

 

아이디어

매번 다른 나무를 잘라야 한다면 나무들이 자라는 길이 Ai 가 가장 작은 것부터 순서대로 자르는 것이 가장 많은 양을 얻을 수 있는 방법이다. 

 

다만 이 문제에서는 '같은 나무를 여러 번 자를 수 있다'고 하고 있다. 이로 인해 마치 매일 가장 높은 나무를 확인해서 이를 잘라가야 할 것처럼 보인다.

 

하지만 실제로는 같은 나무를 여러 번 자를 이유가 없다. 

동일한 나무를 3번 자르든 2번 자르든 5번 자르든 1번 자르든 마지막으로 자르는 날만 동일하다면 그 나무로부터 얻을 수 있는 양은 동일하기 때문이다.

 

따라서 나무 A > B > C 가 있다고 했을 때 A 를 3번 자르는 방법은 C -> B -> A 로 자르는 방법에 비해서 C + B 만큼을 덜 얻게 되는 방법이므로 최대 양을 얻을 수 없다.

 

결국 매번 다른 나무를 자르는 것이 가장 최선의 방법이므로 성장 속도(Ai) 가 작은 나무부터 잘라가면 된다.

 

 

풀이코드

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));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        long result = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            result += Integer.parseInt(st.nextToken());
        }

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

        Arrays.sort(A);
        for (int i = 0; i < n; i++) {
            result += (long)A[i] * i;
        }

        System.out.println(result);
    }
}