2613 숫자구슬 - 백준

숫자구슬 스페셜 저지

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

6966

1770

1185

26.755%

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

8 3
5 4 2 6 9 3 8 7

예제 출력 1 복사

17
4 2 2

출처

Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 고등부 4번

• 데이터를 추가한 사람: deuslovelt, jyheo98, logwns, yclock, ynifamily3
• 문제의 오타를 찾은 사람: pkcchoi3
• 빠진 조건을 찾은 사람: upple1

풀이

첫번째 줄

n개의 숫자구슬, m개의 그룹

2번째 줄

n개의 들어오는 숫자들

 

dp로 풀이

1. 먼저 들어오는 모든 data들을 n*n 배열안에 부분합으로 저장

2. start부터 시작해서 그룹의 갯수를 하나 적게 해서 현재 저장된 부분합의 갯수들을 체크해서 가장 적은 수가 되는 것이 무엇인지 check

3. dp에 들어가는 data는 입력된 data에서 값을 추가해서 출력 반복

4. count도 미리 계산해서 check

코드

package test2613;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	static int n, m;
	static int sumArr[][];
	static int dp[][];
	static int count[][];

	static int solve(int start, int cnt) {
		int min = 987654321;

		// 그룹의 갯수가 1개인 경우
		if (cnt == 1) {
			// 그룹에 포함되는 숫자의 갯수는 전체 - 시작지점 + 1
			count[start][cnt] = n - start + 1;
			// dp 배열에 현재 sumArr 배열[시작][그룹]값을 대입하고 return
			return dp[start][cnt] = sumArr[start][n];
		}
		
		// dp 배열에 현재 시작지접, 그룹 갯수의 값이 0이 아닌 경우 dp 값 return
		if (dp[start][cnt] != 0) {
			return dp[start][cnt];

		}
		
		// 0인 경우 비교를 위해 dp 값을 max치로 변경한다.
		dp[start][cnt] = 987654321;

		// 현재 시작지점부터 전체 - 그룹의 갯수계산한 index 번호까지 전부 비교한다.
		for (int i = start; i <= n - cnt + 1; i++) {
			/*
			 * 점화식: 현재 count 값은 시작지점부터 i번째까지와 i+1번째에서부터 그룹 -1번째까지의 dp 배열값까지의 값을 계산해서 더 작은 것을 구한다.
			 * max(sumArr[시작지점][i번째], solve(i+1번째, 그룹 -1)) <- 이유: 앞에께 1개, 그리고 뒤에께 그룹 -1이기 때문이다.
			 */
			int temp = Math.max(sumArr[start][i], solve(i + 1, cnt - 1));
			// 현재 min값이 temp값보다 큰 경우 교체
			if (temp < min) {
				min = temp;
				// count의 값은 각 그룹의 갯수이므로 이를 표기해준다.
				count[start][cnt] = i - start + 1;
			}
		}

		//dp[시작지점][그룹]의 값은 min 값으로 변경후 return 한다.
		return dp[start][cnt] = min;
	}

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner(System.in);

		dp = new int[301][301];
		sumArr = new int[301][301];
		count = new int[301][301];

		n = sc.nextInt();
		m = sc.nextInt();

		for (int i = 1; i <= n; i++) {
			int input = sc.nextInt();
			for (int j = 1; j <= i; j++) {
				sumArr[j][i] += sumArr[j][i - 1] + input;
			}
		}
		
		
		/* 전부 계산한 값 배열 하나 만듬
		 * [
		 *  [0, 0, 0, 0,  0,  0,  0,  0,  0 ],   
		 *  [0, 5, 9, 11, 17, 26, 29, 37, 44], <- 모든 수를 더한 값
		 *  [0, 0, 4, 6,  12, 21, 24, 32, 39], <- 2번째부터 끝까지 더한값
		 *  [0, 0, 0, 2,  8,  17, 20, 28, 35], 
		 *  [0, 0, 0, 0,  6,  15, 18, 26, 33],
		 *  [0, 0, 0, 0,  0,  9,  12, 20, 27], 
		 *  [0, 0, 0, 0,  0,  0,  3,  11, 18], 
		 *  [0, 0, 0, 0,  0,  0,  0,  8,  15], 
		 *  [0, 0, 0, 0,  0,  0,  0,  0,  7 ]  <- n번째부터 n번째까지 더한 값
		 * ]
		 */
		sc.write(solve(1, m) + "\n");

		for (int i = 1, j = m; j > 0; i += count[i][j], j--) {
			sc.write(count[i][j] + " ");
		}
		sc.write("\n");

		sc.close();

	}

	static class MyScanner {
		final BufferedReader reader;
		final BufferedWriter writer;
		static StringTokenizer tokenizer = null;

		MyScanner(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			writer = new BufferedWriter(new OutputStreamWriter(System.out));
		}

		String nextToken() throws IOException {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}

			return tokenizer.nextToken();
		}

		int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(nextToken());
		}

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(nextToken());
		}

		void write(String sb) throws IOException {
			writer.write(sb);
		}

		void close() throws IOException {
			reader.close();
			writer.close();
		}
	}
}