BOJ 14247 나무 자르기 (Java)

문제 탐색하기

• 총 N개의 나무를 N일씩 오르면서, 하나씩 자른다.
• 나무의 자라는 속도는 각 나무마다 정해져 있다.
• i번째 나무를 한번 자르면, 다음날 나무의 길이는 H[i]만큼 자라난다.
• 정답을 저장할 때는 long(64비트 정수)을 사용해야 한다.
• 최대값이 int 범위를 훨씬 초과하기 때문에, int를 사용하면 오버플로우가 발생할 수 있다.

최대값 추정

문제의 조건은 다음과 같다.

• 1 ≤ N ≤ 100,000
• 1 ≤ H[i], A[i] ≤ 10,000

모든 H[i] = 10,000, A[i] = 10,000, N = 100,000일 때

1. 초기 높이 합
   Σ H[i] = 10,000 × 100,000 = 1,000,000,000
2. 성장률에 따른 증가량 합
   Σ (A[i] × i) = Σ (10,000 × i) (i = 0 ~ 99,999)
3. 총합
   총합 = 1,000,000,000 + 49,999,500,000,000 = 49,999,501,000,000 ( 약 5 × 10¹³)

정답 결과값으로 int의 최대값인 21억을 훨씬 초과하므로 long을 사용해야 함에 유의하자.

코드 설계하기

구현 방법

• 자라는 속도가 가장 작은 순서대로 나무를 잘라야 나무를 가장 많이 자를 수 있다.
  • Tree 클래스 배열을 H 기준으로 정렬한다.
    • 정렬을 위해 Tree 클래스를 Comparable의 구현체로 한다.
• iteration을 수행하면서, 하루마다 잘라갈 수 있는 나무를 최대한 잘라간다.

시간 복잡도

• 입력 및 정답을 구하는 이터레이션은 O(N)
• 배열의 정렬 시간복잡도는 O(N log N)
• 따라서 최대 연산 수는 N log ​N ≈ 100,000 × 16.61 ≈ 1.66×10⁶
  • 주어진 시간(2초) 이내에 연산이 가능하다.

정답 코드 (Java)

import java.io.*;  
import java.util.Arrays;  
import java.util.StringTokenizer;  
  
public class boj14247 {  
    private static int N;  
    private static long res;  
    private static Tree[] trees;  
  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        N = Integer.parseInt(st.nextToken());  
  
        trees = new Tree[N];  
        st = new StringTokenizer(br.readLine());  
  
        for (int i = 0; i < N; i++) {  
            trees[i] = new Tree();  
            trees[i].H = Integer.parseInt(st.nextToken());  
        }  
  
        st = new StringTokenizer(br.readLine());  
        for (int i = 0; i < N; i++) {  
            trees[i].A = Integer.parseInt(st.nextToken());  
        }  
  
        // 자라는 길이 순서대로 정렬한다.  
        Arrays.sort(trees);  
  
        res = 0;  
        // 하루마다[i] 잘라갈 수 있는 나무를 최대한 잘라간다.  
        for (int i = 0; i < N; i++) {  
            res += trees[i].A * i + trees[i].H;  
        }  
  
        System.out.println(res);  
        br.close();  
    }  
  
    static class Tree implements Comparable<Tree> {  
        int H;  
        int A;  
  
        @Override  
        public int compareTo(Tree o) {  
            return this.A - o.A;  
        }  
    }  
}

’’