백준 14247 - 나무 자르기 (자바 - 그리디)

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

14247번: 나무 자르기

 

* 문제 요약

영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n 개의 나무가 있는데, 영선이는 하루에 한 나무씩 n 일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 나무들이 밤만 되면 매우 빠른 속도로 자라는데, 그 자라는 길이는 나무마다 다르다.

따라서, 어느 나무를 잘라가느냐에 따라 총 구할 수 있는 나무의 양이 다른데, 나무의 처음 길이와 하루에 자라는 양이 주어졌을 때, 영선이가 얻을 수 있는 최대 나무 양을 구하시오.

참고로, 자른 이후에도 나무는 0 부터 다시 자라기 때문에 같은 나무를 여러번 자를 수는 있다.

 

* 입력

첫째 줄에는 나무의 갯수 n 개가 있다. 나무는 1번부터 n번까지 있다.

다음 줄에는 첫날 올라갔을 때 나무의 길이들 Hi 가 순서대로 n개만큼 주어진다.

그 다음 줄에는 나무들이 자라는 길이 Ai 가 n개만큼 순서대로 주어진다.

 

* 출력

영선이가 나무를 잘라서 구할 수 있는 최대 양을 출력하시오.

 

* 제한

- 1 <= n <= 100,000

- 1 <= Hi <= 100,000

- 1 <= Ai <= 10,000

 

* 예시

 

* 해결 과정

매 반복마다 가장 긴 나무를 자르는 방식이 아니라, 가장 적게 자라는 나무부터 가장 많이 자라는 나무 순서대로 자를 때 최대값을 구할 수 있다.

기본적으로 자르기 전에 나무 별로 자르는 타이밍에 따라 성장할 수 있는 최대값만큼 나무 길이를 늘려준 다음, 순서대로 전부 다 합산해주면 된다.

 

나무의 현재 길이(value) 와 하루가 지났을 때 자라는 길이(growValue) 를 저장하는 객체 Tree 를 만들고 Comparable 인터페이스를 구현하여 compareTo() 메소드를 오버라이드 한 다음 하루가 지났을 때 자라는 길이를 기준으로 오름차순 정렬할 수 있도록 코드를 다시 작성해준다.

이후 아래와 같은 로직을 따른다.

1. 입력받은 값들을 기준으로 객체를 만든 다음 배열에 저장해준다.

2. Arrays.sort() 메소드를 통해 하루가 지났을 때 자라는 길이를 기준으로 오름차순 정렬해준다.

3. 반복문을 통해 각 나무들을 순차적으로 자를 때 그 나무가 하루에 자랄 수 있는 길이를 기준으로 자랄 수 있는 최대 길이를 구해준다.

4. 모든 길이를 합산해준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int count = Integer.parseInt(br.readLine());
        String[] tree = br.readLine().split(" ");
        String[] grow = br.readLine().split(" ");

        Tree[] treeArray = new Tree[count];
        for (int i = 0; i < count; i++) {
            int value = Integer.parseInt(tree[i]);
            int growValue = Integer.parseInt(grow[i]);
            Tree treeObject = new Tree(value, growValue);

            treeArray[i] = treeObject;
        }

        long result = 0;
        Arrays.sort(treeArray);

        for (int i = 0; i < count; i++) {
            treeArray[i].value += (treeArray[i].growValue * i);
        }
        for (int i = 0; i < count; i++) {
            result += treeArray[i].value;
            treeArray[i].value = 0;
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();

    }
}

class Tree implements Comparable<Tree> {
    int value;
    int growValue;

    public Tree(int value, int growValue) {
        this.value = value;
        this.growValue = growValue;
    }

    @Override
    public int compareTo(Tree arg0) {
        return this.growValue - arg0.growValue;
    }
}

 

현재 상황에서 최적의 해답을 선택한다. -> 하루에 자라는 길이를 기준으로 오름차순 정렬해준 배열을 기준으로 각 나무를 자르는 타이밍에 맞춰 길이를 늘려준 다음, 반복문을 통해 각 나무들의 길이를 더해준다.

선택된 해답이 조건을 만족하는지 검사한다. -> 모든 길이를 합산할 때 까지 얻을 수 있는 나무의 최대 길이를 알 수 없으므로 배열의 모든 요소에 대해 합산을 수행할 때 까지 반복문을 수행한다.

 

위의 과정을 통해 문제를 해결하였으므로 그리디 알고리즘 문제에 해당한다.