10-13: 팀 나누기

팀 나누기

 

문제

---

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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class dp_team_split {

    /**
     팀 나누기
     * 문제:
     * 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
     *
     *
     * @param args
     */

    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];
        int[] sum = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            if (i==0) {
                sum[i] = arr[0];
            } else{
                sum[i] = sum[i-1] + arr[i];
            }
//            System.out.println("sum[" + i+"]: " + sum[i]);
        }

        int[][] dp = new int[N+1][M+1];


        for(int i=1;i<=N;i++){
            dp[i][0] = Integer.MAX_VALUE;
        }

        for(int i=1;i<N+1;i++){
            for(int j=1;j<M+1;j++){
                if(i>j){
                    int n = Integer.MAX_VALUE;
                    for(int k=j;k<=i;k++){

                        int ssum = k>=2? ((sum[i-1]-sum[k-2])) : sum[i-1];

                        int mi = Math.max(ssum,dp[k-1][j-1]);
                        n = Math.min(n,mi);
                    }
                    dp[i][j] = n;
                }
                else if(j==i){
                    int n=Integer.MIN_VALUE;
                    for(int k=0;k<i;k++){
                        n=Math.max(n,arr[k]);
                    }
                    dp[i][j] = n;
                }else{
                    dp[i][j] = 0;
                }
            }
        }

        System.out.println (dp[N][M]);

    }

}