백준 2613번 - 숫자구슬 java
문제
N개의 숫자 구슬이 <그림 1>과 같이 막대에 꿰어져 일자로 놓여 있다. 이들 구슬은 막대에서 빼낼 수 없고, 바꿀 수 없다.
이 숫자 구슬을 M개의 그룹으로 나누었을 때 각각의 그룹의 합 중 최댓값이 최소가 되도록 하려 하다. 예를 들어 세 그룹으로 나눈다고 할 때 <그림 2>와 같이 그룹을 나누면 그룹의 합은 각각 11, 15, 18이 되어 그 중 최댓값은 18이 되고, <그림 3>과 같이 나누면 각 그룹의 합은 각각 17, 12, 15가 되어 그 중 최댓값은 17이 된다. 숫자 구슬의 배열이 위와 같을 때는 그룹의 합 중 최댓값이 17보다 작게 만들 수는 없다. 그룹에 포함된 숫자 구슬의 개수는 0보다 커야 한다.
각 그룹의 합 중 최댓값이 최소가 되도록 M개의 그룹으로 나누었을 때, 그 최댓값과 각 그룹을 구성하는 구슬의 개수를 찾아 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100 이하의 자연수이다.
출력
각 그룹의 합 중 최댓값이 최소가 되도록 M개의 그룹으로 나누었을 때 그 최댓값을 첫째 줄에 출력하고, 둘째 줄에는 각 그룹을 구성하는 구슬의 개수를 왼쪽부터 순서대로 출력한다. 구슬의 개수를 출력할 때는 사이에 한 칸의 공백을 둔다. 만약 그룹의 합의 최댓값이 최소가 되도록 하는 경우가 둘 이상이라면 그 중 하나만을 출력한다.
해결 방법
예시의 구슬을 보도록 하자
이 구슬 목록에서 우선 젤 첫 번째 구슬인 5를 이용해 1개의 그룹을 만든다고 생각해보자. 그러면 최댓값은 5가 되고, 그룹의 개수는 1개가 된다. 그리고 그 다음 4라는 구슬을 고려하여, 1개의 그룹을 만든다고 하면 최댓값은 9가 된다.
구슬이 두 개면 그룹을 2개 까지 만들 수 있으므로, 4가 들어왔을 때 그룹의 개수를 2개로 만들려면, 최댓값은 5가 된다.
이 때 다음 2라는 구슬이 들어온다고 했을 때, 2라는 구슬까지 고려했을 때 1개의 그룹을 만들었을 때 최대값은 11이 된다.
그러나 2가 들어왔을 때 문제의 조건을 만족하며 2개의 그룹을 만들려면 어떤 방법을 써야할까? 2가 들어왔을 때 2개의 그룹으로 나누는 방법은, 5,4로 이루어진 1개의 그룹을 만든 것과 2로 이루어진 그룹을 비교하거나, 5로 이루어진 그룹을 만들고 4와 2로 이루어진 그룹을 만들는 방법이 있다.
즉 i개의 구슬을 이용하여 j개의 그룹을 만들었다고 쳤을 때, 그 다음 구슬이 들어와서 문제의 조건을 만족하는 j개의 그룹을 만들려고 한다면 이것을 나타내는 dp 배열을 다음과 같이 정의할 수 있다.
dp[i][j] = i개의 수를 j개의 그룹으로 나누었을 때 최소가 되는 최댓값
그리고 점화식은 다음과 같이 나타낼 수 있다.
dp[i][j] = (k 는 i..1) min(dp[k-1][j-1], sum(i..k))
dp[i][j] 가 갱신 됐을 때 제일 마지막 그룹의 원소 개수는 (i-k+1) 개가 된다. i개의 수를 j개의 그룹으로 나누었을 때 제일 우측에 있는 집합의 원소의 수를 담는 배열을 count[i][j] 라고 해보자.
dp[i][j] 가 갱신 될 때, count[i][j] 의 값은 i-k+1 이 된다 (제일 우측 집합의 개수가 i-k+1 일 때, 각 그룹의 합의 최댓값이 최소값이 됨)
즉 그룹의 합의 최솟값이 되는 정답이 dp[i][j] 에 저장될 때, 제일 우측 집합의 원소의 수는 count[i][j] 에 저장되고 그 다음 바로 왼쪽 집합의 원소의 수는 count[i - count[i][j]][j-1] 에 저장된다. 이것을 역추적하면 각 그룹의 원소의 수를 구할 수 있다.
public class P2613 {
static int[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(in));
StringBuilder sb = new StringBuilder();
StringTokenizer input = new StringTokenizer(br.readLine());
int N = Integer.parseInt(input.nextToken()); //구슬의 개수
int M = Integer.parseInt(input.nextToken()); //그룹의 수
arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
solution(N, M);
}
static void solution(int N, int M) {
int[][] dp = new int[N][M + 1]; //N개의 수를 M개의 그룹으로 나누었을 때, 그룹의 합의 최댓값의 최솟값
int[][] count = new int[N][M + 1]; //N개의 수를 M개의 그룹으로 나누었을 때 제일 우측 그룹의 원소의 수
for (int i = 0; i < N; i++) Arrays.fill(dp[i], 987653321);
for (int i = 0, sum = 0; i < N; i++) {
sum += arr[i];
dp[i][1] = sum;
count[i][1] = i + 1; //N개의 수를 1개의 그룹으로 나누면 최댓값은 N개의 수의 합과 같다.
}
for (int i = 0; i < N; i++) {
for (int j = 1; j <= M; j++) {
int sum = 0;
for (int k = i; k >= 1; k--) {
sum += arr[k]; //제일 우측 집합을 하나씩 추가한다.
int thisNumber = Math.max(dp[k - 1][j - 1], sum); //제일 우측 집합과 그 집합을 빼고 만들 수 있는 j-1개 그룹의 최댓값을 비교
if (dp[i][j] > thisNumber) {
count[i][j] = i - k + 1;
dp[i][j] = thisNumber;
}
}
}
}
System.out.println(dp[N - 1][M]);
//제일 우측 집합의 개수부터 역추적해가며 구함
Stack<Integer> stack = new Stack<>();
for (int i = M, temp = N - 1; i >= 1; i--) {
stack.add(count[temp][i]);
temp -= count[temp][i];
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop()).append(" ");
}
System.out.print(sb);
}
}