팀 나누기

문제

---

N명의 학생을 M개의 팀으로 나누려고 한다. 각 학생은 본인의 능력을 나타내는 숫자를 하나씩 갖고 있으며, 편의상 팀을 나눌 때에는 연속한 학생들을 하나의 팀으로 만든다고 하자. 예를 들어, 다음 그림은 10명의 학생을 3개의 팀으로 나누는 두 가지 예이다.

각 팀의 점수는 그 팀에 속한 학생들의 점수의 합이다. 예를 들어, 첫 번째의 경우 각 팀의 점수는 9/7/14 가 되며, 두 번째의 경우에는 4/16/10 이 된다. 팀을 잘 나누기 위해서는, 각 팀의 점수가 비슷해야 한다. 즉, 하나의 팀의 점수가 매우 높아서는 안 된다. 따라서 점수가 최대인 팀의 점수를 최대한 적게 만들고 싶다. 위의 예제에서는 아래와 같이 나누게 되면, 각 팀의 점수가 9/11/10 이 된다. 점수가 최대인 팀은 11이며, 어떻게 하더라도 점수가 가장 높은 팀을 11보다 적게 팀을 나눌 수는 없다.

N명의 학생의 점수와 나누고자 하는 팀의 개수 M이 주어질 때, 점수가 가장 높은 팀이 갖는 점수의 최솟값을 출력하는 프로그램을 작성하시오.

 

입력

---

첫 번째 줄에 학생의 수 N과 나누고자 하는 팀의 개수 M이 주어진다. (1 ≤ N, M ≤ 500) 두 번째 줄에는 N명의 학생의 점수가 주어진다.  

출력

---

점수가 가장 높은 팀이 갖는 점수의 최솟값을 출력한다.

 

예제 입력

10 3
1 3 5 2 2 3 4 6 3 1

예제 출력

11

코드 / 이분탐색

///팀나누기

import java.util.*;

public class Main {

    public static ArrayList<Integer> box = new ArrayList<>();
    public static int result = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int b;
        int c[];
        int d;
        int max = 0;
        int min = 0;
        int cur = 0;

        a = sc.nextInt();
        b = sc.nextInt();
        c = new int[a + 1];
        d = 0;

        for (int i = 1; i <= a; i++) {
            c[i] = sc.nextInt();
            d = c[i] + d;
            if (c[i] > min) min = c[i];
        }

        findMin(c, min, d, b);

        System.out.println(result);

    }

    public static void findMin(int[] c, int s, int r, int b) {
        if (s > r) {
            return;
        } else {
            int mid = (s + r) / 2;

            int isGood = isFind(c, mid, b);

            if (isGood == -1) {
                if (mid < result) result = mid;
                findMin(c, s, mid - 1, b);

            } else findMin(c, mid + 1, r, b);
        }
    }

    public static int isFind(int[] c, int mid, int b) {
        int cur = 0;
        int max = mid;
        for (int i = 1; i < c.length; i++) {
            cur += c[i];
            if (cur > max) {
                cur = c[i];
                b--;
            }
            if (b == 0) return 1;
        }
        return -1;
    }
}