이상한 폭탄 3

문제 개요

N개의 수가 주어질 때, 이 수열을 정확히 M개의 구간으로 나누려고 한다.
이때, 각 구간의 합 중 최댓값이 최소가 되도록 구간을 나누는 프로그램을 작성하라.

• 첫째 줄에 N과 M이 주어지고, 둘째 줄에 N개의 수가 주어진다.
• 2 ≤ M ≤ N ≤ 100
• 각 수는 1 이상 100 이하의 정수이다.
• 출력은 구간 합의 최댓값 중 가능한 값들 중 최소값을 출력한다.

풀이 방식

브루트포스 방식으로 1부터 가능한 최대값 범위(문제에서 10000까지)까지 반복하면서,
각 값 i를 "구간 합의 상한값(최댓값 후보)"라고 가정하고 아래 과정을 수행한다.

1. 주어진 수열을 앞에서부터 순차적으로 훑는다.
2. 현재 합(cnt)에 다음 수를 더했을 때 i를 넘으면 구간을 끊고, 새로운 구간을 시작한다.
3. 이 과정을 반복해 필요한 구간 수(section)를 센다.
4. 구간 수가 M 이하이고, 수 중 어떤 것도 i보다 큰 값이 없으면 정답 후보로 고려한다.

이때 i가 가능한 후보 중 최소값이 되도록 계속 최소값을 갱신한다.

정답 코드 (Java)

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] nums = new int[n];
		for (int i = 0; i < n; i++)
			nums[i] = sc.nextInt();

		int ans = 10000;
		for (int i = 1; i <= 10000; i++) {
			boolean isPassable = true;
			int section = 1;
			int cnt = 0;

			for (int j = 0; j < n; j++) {
				if (nums[j] > i) {
					isPassable = false;
					break;
				}

				if (cnt + nums[j] > i) {
					cnt = 0;
					section++;
				}

				cnt += nums[j];
			}

			if (isPassable && section <= m) {
				ans = Math.min(ans, i);
			}
		}

		System.out.println(ans);
	}
}

핵심 정리

1부터 가능한 최대값까지 순차적으로 구간 합의 상한을 늘려가며, 해당 값으로 M개 이하의 구간으로 나눌 수 있는지만 확인하고, 이를 통해 구간 합의 최대값의 최솟값을 찾는다.
M개 이하로 나눌 수 있다면 일부 구간을 쪼개 정확히 M개로 만들 수 있으므로 정답 후보가 된다.

• 100개의 숫자를 여러개의 구간으로 나누는 경우의 수는 굉장히 많다.
• 숫자들을 모든 구간으로 나누어 완전탐색하기 위해서는 최악의 경우 99C50 = 약 5 * 10^28개의 경우를 세야 한다.
• 구간의 합의 최댓값을 결정한다면 구간을 몇 개로 나눠야 하는지 손쉽게 찾을 수 있다.
• 해당 코드는 M개 이하로 나눌 수 있는지를 확인하고, 그 중 가능한 최소값을 찾는다.
• 문제는 정확히 M개로 나누는 것이지만, section <= M인 경우, 일부 구간(길이 ≥ 2)을 더 쪼개서 정확히 M개로 만드는 것이 가능하므로 정답 후보가 될 수 있다.
• 각 구간의 최대합이 정확히 i와 일치할 필요는 없으며,
• i부터 1씩 증가하며 탐색하므로, 최솟값으로 선택된 i는 반드시 어떤 구성에서 최대값과 일치하거나 가장 근접한 값이 된다.