[Lv.99] 동적 계획법 최적화

박준원·2024년 4월 8일

나무 자르기 문제 해결하기

나무 자르기 문제는 전기톱을 이용하여 나무를 자를 때 발생하는 충전 비용의 최솟값을 구하는 문제입니다. 이를 해결하기 위해서는 주어진 조건에 따라 전기톱을 사용하는 방법을 결정해야 합니다.

1. 문제 해결 방법

주어진 조건에 따라 전기톱을 사용하여 나무를 자르는 경우를 고려해야 합니다.
나무의 높이가 작은 순서대로 전기톱을 사용하는 것이 합리적입니다. 왜냐하면 높은 나무를 먼저 자를 경우에 비용이 더 많이 들기 때문입니다.

알고리즘 설계

입력으로 주어진 나무의 높이와 충전 비용을 배열에 저장합니다.
이전까지의 나무 중에서 가장 높은 나무의 높이를 기록하는 변수를 선언합니다. 처음에는 0으로 초기화합니다.
각 나무를 순회하면서 다음을 수행합니다:
현재 나무의 높이가 이전까지의 가장 높은 나무의 높이보다 높으면, 가장 높은 나무의 높이를 갱신합니다.
현재 나무를 자를 때 발생하는 충전 비용은 현재 나무의 높이와 해당 나무를 자를 때의 충전 비용을 곱한 값입니다. 이 값을 전체 충전 비용에 더합니다.
모든 나무를 순회한 후에는 총 충전 비용을 출력합니다.

2. 코드 설계

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long[] treeHeights = new long[n];
        long[] chargingCosts = new long[n];

        // 나무 높이 입력
        for (int i = 0; i < n; i++) {
            treeHeights[i] = scanner.nextLong();
        }

        // 전기톱 충전 비용 입력
        for (int i = 0; i < n; i++) {
            chargingCosts[i] = scanner.nextLong();
        }

        // 충전 비용의 최솟값 계산
        long totalCost = calculateTotalChargingCost(n, treeHeights, chargingCosts);
        System.out.println(totalCost);
    }

    // 충전 비용의 최솟값 계산하는 함수
    private static long calculateTotalChargingCost(int n, long[] treeHeights, long[] chargingCosts) {
        long totalCost = 0;
        long maxTreeHeight = 0;

        for (int i = 0; i < n; i++) {
            if (treeHeights[i] > maxTreeHeight) {
                maxTreeHeight = treeHeights[i];
            }
            totalCost += maxTreeHeight * chargingCosts[i];
        }

        return totalCost;
    }
}