[240313] 알고리즘 리부트 30일차 - 백준 2805 자바

[Part1-Chapter07-Clip07]

- 백준 2805 나무 자르기

풀고 나니 간단해 보이는데 분기를 짜는데 조금 시간이 걸렸다. 일단 좀 특이한 점은 자르고자 하는 높이를 설정하고 나무가 잘라진 길이를 구할 때 나무를 일단 정렬하고 잘리는 나무들의 시작 인덱스를 이분탐색으로 구했다는 점이다. 

기본적으로 자를 높이는 가져가고자 하는 나무 길이의 최솟값이 1이므로 가장 큰 나무의 길이보다 -1한 값을 r로 설정하고 모두 베어버리는 경우가 가장 긴 나무 길이를 가져 가는 것이므로 l 는 0으로 설정했다. 이분 탐색을 통해 가져가고자 하는 길이와 같은 경우, 짧은 경우, 긴 경우를 분기하여 로직을 구현했다.

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

public class Main {
    static int n, m, max;
    static int[] trees;

    public static void main(String[] args) throws IOException {
        input();

        Arrays.sort(trees);

        long l = 0; // 모든 나무를 뿌리까지 베어야 하는 경우
        long r = max - 1; // m의 최소 길이는 1이기 때문에 가장 큰나무보다 1m 작게 설정
        long h = -1L;

        while (l <= r) {
            long mid = (l + r) / 2;

            // 길이가 mid 일 경우 가져갈 수 있는 나무의 총 길이
            long tmp = getTotalLength(mid);

            if (tmp == m) {
                h = mid;
                break;
            } else if (tmp > m) {
                h = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        System.out.println(h);
    }

    private static long getTotalLength(long mid) {

        int start = 0;
        int end = n - 1;
        int firstIdx = -1;
        long totalLength = 0;

        while (start <= end) {
            int middle = (start + end) / 2;

            if (trees[middle] < mid) {
                start = middle + 1;
            } else if (trees[middle] <= mid) {
                firstIdx = middle;
                start = middle + 1;
            } else {
                firstIdx = middle;
                end = middle - 1;               
            }
        }

        for (int i = firstIdx; i < n; i++) {
            totalLength += trees[i] - mid;
        }
        return totalLength;
    }

    private static void input() throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        trees = new int[n];
        max = 0;
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            trees[i] = Integer.parseInt(st.nextToken());
            max = Math.max(trees[i], max);
        }
    }
}

 

[Part1-Chapter07-Clip08]

- 백준 1654 랜선 자르기

이 문제는 각 랜선은 동일한 길이만 충족하면 되고 해당 길이로 자른 랜선의 갯수가 요구하는 갯수와 일치하면 된다. 여기서 가장 랜선의 길이가 긴 경우를 구하는 문제이다. 기준 길이보다 짧은 랜선이 남았을 경우 버리면 되기 때문에 고려하지 않아도 된다. 이분 탐색으로 길이를 구했는데 의아한 것은 왜 최댓값이 모든 랜선 중 가장 긴 랜선으로 처리하면 틀리고 문제에서 제시한 최대값인 int의 최대 정수를 넣으면 맞느냐는 것이다.. 찾아봤지만 명쾌한 해설을 확인하지 못했고 강의를 들으며 보완해보겠다.

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

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int k = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        int[] wires = new int[k];

        while (--k >= 0) {
            wires[k] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(wires);

        long l = 1;
        long r = Integer.MAX_VALUE;

        long len = -1;


        while (l <= r) {
            long m = (l + r) / 2;

            int tmp = 0;

            for (int i = 0; i < wires.length; i++) {
                tmp += (wires[i] / m);
            }

            if (tmp >= n) {
                l = m + 1;
                len = m;
            } else {
                r = m - 1;
            }
        }

        System.out.println(len);
    }
}