[알고리즘] 백준 2805 나무자르기 -이분탐색- 자바 코틀린

www.acmicpc.net/submit/2805

로그인

 

 

이전 단계인 랜선자르기 문제를 풀었으면 조건만 조금 변경하면 쉽게 풀 수 있는 문제입니다.

문제는 Scanner 를 사용했을때 계속 메모리 초과가 나서 Buffered로 바꿔줬더니 해결되었습니다.

 

풀이는 주석에 정리했습니다.

 

[Java]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

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 N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        int left = 0;
        int right = arr[N - 1];
        while (left <= right) {
            int mid = (left + right) / 2;
            long sum = 0;
            for (int h : arr) {
                if (h - mid > 0) { // 자를수있는 나무인 경우
                    sum += (h - mid);
                }
            }
            if (sum < M) { //필요한 나무길이 부족
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(right);
        br.close();
    }
}

 

 

[Kotlin]

import java.io.BufferedReader
import java.io.IOException
import java.io.InputStreamReader
import java.util.*

@Throws(IOException::class)
fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var st = StringTokenizer(br.readLine())
    val N = st.nextToken().toInt()
    val M = st.nextToken().toInt()
    val arr = IntArray(N)
    st = StringTokenizer(br.readLine())
    for (i in 0 until N) {
        arr[i] = st.nextToken().toInt()
    }
    Arrays.sort(arr)
    var left = 0
    var right = arr[N - 1]
    while (left <= right) {
        val mid = (left + right) / 2
        var sum: Long = 0
        for (h in arr) {
            if (h - mid > 0) { // 자를수있는 나무인 경우
                sum += (h - mid).toLong()
            }
        }
        if (sum < M) { //필요한 나무길이 부족
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    println(right)
    br.close()
}

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!