[백준/Java] 14247번 : 나무 자르기

🌵 문제 분석

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

 

영선이는 n일동안 나무를 하루에 한 개씩 잘라오려고 한다.

나무 n개의 처음 길이와 하루에 자라는 양이 주어질 때,

영선이가 얻을 수 있는 최대 나무의 양을 구하라.

 

입력값 :

나무 개수(n)

나무 n개의 처음 길이

나무들이 자라는 길이

5
1 3 2 4 6
2 7 3 4 1

🌵 구현 아이디어

🤔 가장 빨리 자라는 나무를 먼저 베는 게 유리하다? vs 현재 길이가 긴 나무를 먼저 베는 게 유리하다?

처음에는 가장 빨리 자라는 나무를 가장 빨리 베는 게 유리할 거라고 생각했다.

(그냥 베어서 0이 되어도 빨리 자라니까..?라는 근거 없는 아이디어였음)

 

💡 가장 빨리 자라는 나무를 가장 나중에 베는 게 유리하다

각 날에 자라는 나무의 길이를 나열해본 후

가장 빨리 자라는 나무를 가장 나중에 베는 게 유리하다는 것을 깨달았다.

 

예제 입력 1의 경우

5
1 3 2 4 6
2 7 3 4 1

1~5번째 날에 벨 수 있는 나무의 길이는 다음과 같다.

	첫 번째 나무	두 번째 나무	세 번째 나무	네 번째 나무	다섯 번째 나무
성장 속도	2	7	3	4	1
첫째 날	1	3	2	4	6
둘째 날	3	10	5	8	7
셋째 날	5	17	8	12	8
넷째 날	7	24	11	16	9
다섯째 날	9	31	14	20	10

영선이가 가져갈 수 있는 가장 긴 길이는 31이다. 

즉 성장 속도가 가장 빠른 나무를 가장 길게 자랄 때까지(마지막 날까지) 기다렸다가 베는 게 유리하다.

 

이 아이디어를 다른 나무들에도 적용시켜보면, 성장 속도가 느린 나무부터 하나씩 베어야 최대 양을 얻을 수 있다.

	첫 번째 나무	두 번째 나무	세 번째 나무	네 번째 나무	다섯 번째 나무
성장 속도	2	7	3	4	1
첫째 날	1	3	2	4	6
둘째 날	3	10	5	8	7
셋째 날	5	17	8	12	8
넷째 날	7	24	11	16	9
다섯째 날	9	31	14	20	10

 

👉🏻 디테일한 근거 찾기

현재 나무 길이가 더 크든 작든 상관 없이

성장 속도가 1만큼만 빨라도 더 나중에 베는 게 유리하다.

 

예를 들어 두 나무가 있다고 가정해보자.

나무 1은 초기 길이가 10, 성장 속도가 2

나무 2는 초기 길이가 6, 성장 속도가 1

 

첫째 날 길이만 보면 길이가 더 긴 나무1을 베어야 할 것 같지만, 성장 속도가 더 빠르므로 나중에 베어야 한다.

나무1 먼저 베면 10+7=17

나무2 먼저 베면 12+6=18

	나무1	나무2
첫째 날	10	6
둘째 날	12	7

 

🤔 자라는 속도가 같은 나무가 있다면?

나무 1은 초기 길이가 10, 성장 속도가 2

나무 2는 초기 길이가 6, 성장 속도가 2

	나무1	나무2
첫째 날	10	6
둘째 날	12	8

 

나무 1은 초기 길이가 10, 성장 속도가 2

나무 2는 초기 길이가 1, 성장 속도가 2

	나무1	나무2
첫째 날	10	1
둘째 날	12	3

 

어느 것을 먼저 선택해도 상관 없다.

🤔 같은 나무를 또 베는 경우?

같은 나무를 또 베면 최적의 해를 구할 수 없다.

 

같은 나무를 n번 베고 자라기를 기다리는 행위를 반복해서 얻을 수 있는 길이 == 그 나무를 n일 후에 베었을 때 얻을 수 있는 길이

이므로 같은 나무를 n번 반복해서 베는 것은 벨 수 있는 기회를 무의미하게 소진하는 것이다.

 

그 기회를 다른 나무를 베는 데 쓰면 결과적으로 더 긴 길이를 얻을 수 있다.

-> n개의 나무를 각각 한 번씩 베는 것이 최적의 방법이다.

🌵 시간 복잡도

n개의 나무를 자라는 속도 순서대로 정렬한 후,

- Java의 Arrays.sort()는 timesort를 사용하므로 최악의 경우 시간 복잡도는 O(nlogn) 

 

각 나무에게서 n일차에 얻을 수 있는 길이를 구하여 합을 출력한다.

- n개의 나무에 대해 길이를 구하는 시간 복잡도는 O(n)*O(1)

 

따라서 전체 시간 복잡도는 O(nlogn)*O(n)*O(1)인데 n은 최대 100,000이므로 

5*100,000*1 < 2억

-> 제한 시간(2초) 내에 연산 가능하다.

🌵 알고리즘

각 단계에서 성장 속도가 느린 나무를 최적해로 선택하여 최종 해를 구하고 있으므로

그리디 알고리즘에 해당한다.

🌵 오답 노트

영선이가 얻을 수 있는 나무의 최대 길이를 long타입으로 받을 수 있게 수정하였음

 

- 초기 길이(H)가 최대 100,000

- 자랄 수 있는 길이(A)가 최대 10,000

- 나무 개수(n)는 최대 100,000개

 

영선이가 얻을 수 있는 나무의 길이 : 

(초기 길이 * 나무 개수) + (자랄 수 있는 길이 * 나무 개수) + (자랄 수 있는 길이 * 나무 개수 -1) + ... + (자랄 수 있는 길이 * 1)

= H*n + A*n + A*(n-1) + ... + A*1

= 1,000,000,000자리 이상

 

int

32bit = 4byte

범위 : -2,147,483,648 ~ 2,147,483,647

 

long

64bit = 8byte

범위 : -9223372036854775808 ~ 9223372036854775807

🌵 코드 설계

1. 입력 받기
   1. int 변수에 n을 입력받음
   2. 배열에 나무 길이(tree), 자라는 속도(v)를 입력받음
   3. '나무 길이', '자라는 속도'를 변수로 가지는 Tree객체 생성
   4. trees 배열에 Tree 객체 넣기
2. trees 배열을 나무의 자라는 속도를 기준으로 내림차순 정렬
3. 정렬된 값을 사용해 차례로 v[0]*(n-1), v[1]*(n-2), ..., v[n-1]*(0) 구하기
   -> 나무를 베는 시점에 누적된 자란 길이
4. 나무의 초기 길이까지 더해준 후 정답 출력

🌵 정답 코드

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        //trees에 초기 나무 길이, 자라는 속도 객체 저장
        Tree[] trees = new Tree[n];
        for (int i = 0; i < n; i++) {
            int initLen = Integer.parseInt(tree[i]);
            int velocity = Integer.parseInt(v[i]);
            trees[i] = new Tree(initLen, velocity);
        }

        //trees를 자라는 속도 기준으로 내림차순 정렬
        Arrays.sort(trees);
        
        //얻을 수 있는 최대 길이 구하기
        long ans = 0;
        for(int i=0; i<n; i++){
            //해당 나무를 베는 날 누적된 자란 길이
            ans += (long) trees[i].velocity *((n-1)-i);
            //해당 나무의 초기 길이
            ans += Long.parseLong(tree[i]);
        }

        bw.write(ans+" ");
        bw.close();

    }
}
class Tree implements Comparable<Tree>{

    int initLen, velocity;

    Tree(int initLen, int velocity){
        this.initLen = initLen;
        this.velocity = velocity;
    }

    @Override
    public int compareTo(Tree o) {
        return o.velocity - this.velocity;
    }
}