백준 13702번
https://www.acmicpc.net/problem/13702

문제

---

생각하기

---

• 이분 탐색 알고리즘 문제이다.

  • mid는 막걸리를 K명 인원에게 분배할 수 있는 최대량.

  • N 개의 주전자에 mid 만큼 분배해서 남는 양

  • 즉, 하나의 주전자에서 mid 미만의 양이 남을 경우 버린다

동작

코드

---

Java

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

public class Main {
    private static int N;
    private static int K;
    private static long[] potArr;
    private static long result = Long.MIN_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        potArr = new long[N];

        long max = Long.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            potArr[i] = Long.parseLong(br.readLine());
            max = Math.max(potArr[i], max);
        }

        binarySearch(1, max);

        sb.append(result);
        bw.write(sb.toString());
        bw.close();
    } // End of main

    private static long binarySearch(long low, long high) {
        if (low > high) {
            return -1;
        }

        long mid = (low + high) / 2;
        int count = check(mid);

        if (K <= count) {
            result = Math.max(result, mid);
            long temp = binarySearch(mid + 1, high);

            if (temp == -1) {
                return mid;
            } else {
                return temp;
            }
        } else {
            return binarySearch(low, mid - 1);
        }
    } // End of binarySearch

    private static int check(long mid) {
        int count = 0;
        for (long pot : potArr) {
            count += pot / mid;
        }
        return count;
    } // End of check
} // End of Main class

Kotlin

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


private var N = 0
private var K = 0
private lateinit var potArr: IntArray
private var result = Long.MIN_VALUE

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))
    val sb = StringBuilder()

    val st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt() // 주전자의 개수
    K = st.nextToken().toInt() // 은상이를 포함한 친구들의 수
    potArr = IntArray(N)

    var max = Int.MAX_VALUE
    for (i in 0 until N) {
        potArr[i] = br.readLine().toInt()
        max = Math.max(potArr[i], max)
    }

    binarySearch(1, max.toLong())

    sb.append(result)
    bw.write(sb.toString())
    bw.close()
} // End of main

private fun binarySearch(low: Long, high: Long): Long {
    if (low > high) {
        return -1
    }

    val mid: Long = (low + high) / 2
    val cnt = check(mid)

    if (K <= cnt) {
        result = Math.max(result, mid)
        val temp = binarySearch(mid + 1, high)
        if (temp == -1L) {
            return mid
        } else {
            return temp
        }
    } else {
        return binarySearch(low, mid - 1)
    }
} // End of binarySearch

private fun check(mid: Long): Int {
    var cnt = 0
    potArr.forEach { pot ->
        cnt += (pot / mid).toInt()
    }
    return cnt
} // End of check