[SW Expert Academy, SWEA 11446] 사탕 가방 (java)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXdHxTNqC2IDFAS5&categoryId=AXdHxTNqC2IDFAS5&categoryType=CODE&problemTitle=11446&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

---

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

728x90

---

메모리: 27,140 KB, 시간: 147 ms

사용 알고리즘: 이분탐색

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

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder result = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            long M = Long.parseLong(st.nextToken());

            Long[] candies = new Long[N];
            st = new StringTokenizer(br.readLine());
            long m = 0;
            for (int i = 0; i < N; i++) {
                candies[i] = Long.parseLong(st.nextToken());
                m = Math.max(m, candies[i]);
            }

            long s = 1, e = m;
            long ans = 0;
            while(s <= e) {
                long mid = (s + e) / 2;
                long p = M;

                for (int i = 0; i < N; i++) {
                    p -= (candies[i] - (candies[i] % mid)) / mid;
                    if(p <= 0) break;
                }

                if(p <= 0) {
                    ans = Math.max(ans, mid);
                    s = mid + 1;
                }
                else e = mid - 1;
            }

            result.append("#" + tc + " " + ans + "\n");
        }

        System.out.println(result);
    }
}