BOJ_2613_숫자구슬(Java)

[Gold II] 숫자구슬 - 2613

문제 링크

성능 요약

메모리: 16320 KB, 시간: 144 ms

분류

이분 탐색, 다이나믹 프로그래밍, 그리디 알고리즘, 매개 변수 탐색

제출 일자

2024년 8월 21일 13:59:16

문제 설명

N개의 숫자 구슬이 <그림 1>과 같이 막대에 꿰어져 일자로 놓여 있다. 이들 구슬은 막대에서 빼낼 수 없고, 바꿀 수 없다.

이 숫자 구슬을 M개의 그룹으로 나누었을 때 각각의 그룹의 합 중 최댓값이 최소가 되도록 하려 하다. 예를 들어 세 그룹으로 나눈다고 할 때 <그림 2>와 같이 그룹을 나누면 그룹의 합은 각각 11, 15, 18이 되어 그 중 최댓값은 18이 되고, <그림 3>과 같이 나누면 각 그룹의 합은 각각 17, 12, 15가 되어 그 중 최댓값은 17이 된다. 숫자 구슬의 배열이 위와 같을 때는 그룹의 합 중 최댓값이 17보다 작게 만들 수는 없다. 그룹에 포함된 숫자 구슬의 개수는 0보다 커야 한다.

각 그룹의 합 중 최댓값이 최소가 되도록 M개의 그룹으로 나누었을 때, 그 최댓값과 각 그룹을 구성하는 구슬의 개수를 찾아 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100 이하의 자연수이다.

출력

각 그룹의 합 중 최댓값이 최소가 되도록 M개의 그룹으로 나누었을 때 그 최댓값을 첫째 줄에 출력하고, 둘째 줄에는 각 그룹을 구성하는 구슬의 개수를 왼쪽부터 순서대로 출력한다. 구슬의 개수를 출력할 때는 사이에 한 칸의 공백을 둔다. 만약 그룹의 합의 최댓값이 최소가 되도록 하는 경우가 둘 이상이라면 그 중 하나만을 출력한다.

문제풀이

DP를 이용한 풀이

코드

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

public class Main {
    static int a[], sum[], dp[][], n, m;
    static BufferedReader br;
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        
        a = new int[305];
        sum = new int[305];
        dp = new int[305][305];
        
        st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        for (int[] row : dp) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
            sum[i] = sum[i - 1] + a[i];
            dp[i][1] = sum[i];
        }

        dp[0][0] = 0;

        for (int i = 1; i <= m; i++) { // 그룹 수
            for (int j = 1; j <= n; j++) { // 구슬 수
                for (int k = 1; k <= j; k++) {
                    dp[j][i] = Math.min(dp[j][i], Math.max(dp[j - k][i - 1], sum[j] - sum[j - k]));
                }
            }
        }

        System.out.println(dp[n][m]);
        makeAns(n, m);
    }
    
    private static void makeAns(int j, int i) {  
    	if (i == 0 && j == 0) {
    		return;
    	}
    	for (int k = j; k >= 1; k--) {
    		if (Math.max(dp[j - k][i - 1], sum[j] - sum[j - k]) == dp[j][i]) {
    			makeAns(j - k, i - 1);
    			System.out.print(k + " ");
    			return;
    		}
    	}
    }
}