백준 9699 - RICE SACK [Java]

문제

Several sacks of rice need to be transported to five Orphanage Houses. The heaviest sack will go to Orphanage House Al-Ameen because it has the most number of orphanges. The lightest will be sent to Orphanage House Mutiara due to the small number of children staying there. Given a row of rice sacks, decide which sack goes to Al-Ameen?

• 입력
  The first line is an integer that represent the number of case. The following lines have 5 integers indicating the weights of 5 rice sacks, each separated by a blank. No sack will have a weight of more than 100 unit.
• 출력
  For each test case, the output contains a line in the format Case #x: followed by a sequence of integers, where x is the case number (starting from 1) and an integer that indicates the weight of a rice sack that will go to Al-Ameen.

예제 입력	예제 출력
4 1 6 10 5 20 5 10 25 3 1 30 15 5 1 8 7 4 20 50 5	Case #1: 20 Case #2: 25 Case #3: 30 Case #4: 50

---

코드

import java.util.*;

public class Main {
    private static final int N = 5;
    private static final int[] arr = new int[N];
    private static final int[] tree = new int[N*4];

    private static void init(int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
            return;
        }
        int mid = (start + end) / 2;
        init(node*2, start, mid);
        init(node*2+1, mid+1, end);
        tree[node] = Math.max(tree[node*2], tree[node*2+1]);
    }

    private static int query(int node, int start, int end, int left, int right) {
        if (right < start || end < left) {
            return Integer.MIN_VALUE;
        }
        if (left <= start && end <= right) {
            return tree[node];
        }
        int mid = (start + end) / 2;
        int l = query(node*2, start, mid, left, right);
        int r = query(node*2+1, mid+1, end, left, right);
        return Math.max(l, r);
    }

    private static void update(int node, int start, int end, int index, int value) {
        if (index < start || index > end) {
            return;
        }
        if (start == end) {
            arr[index] = value;
            tree[node] = value;
            return;
        }
        int mid = (start + end) / 2;
        update(node*2, start, mid, index, value);
        update(node*2+1, mid+1, end, index, value);
        tree[node] = Math.max(tree[node*2], tree[node*2+1]);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        for (int t = 1; t <= T; t++) {
            for (int i = 0; i < N; i++) {
                arr[i] = scanner.nextInt();
            }
            init(1, 0, N-1);
            int max = query(1, 0, N-1, 0, N-1);
            // int max = Arrays.stream(arr).max().getAsInt();
            System.out.printf("Case #%d: %d\n", t, max);
        }
        scanner.close();
    }
}

• 참고자료: BOJBOOK - 세그먼트 트리
• 사실 세그먼트 트리는 굳이 쓸 필요 없고, 그냥 배열의 최대값만 출력해도 된다.