[BOJ] 백준 13397번 구간 나누기 2 (Java)

#13397 구간 나누기 2

난이도 : 골드 4 

유형 : 파라메트릭 서치 / 이진 탐색

13397번: 구간 나누기 2

▸ 문제

N개의 수로 이루어진 1차원 배열이 있다. 이 배열을 M개 이하의 구간으로 나누어서 구간의 점수의 최댓값을 최소로 하려고 한다. 구간은 다음과 같은 조건을 만족해야 한다.

1. 하나의 구간은 하나 이상의 연속된 수들로 이루어져 있다.
2. 배열의 각 수는 모두 하나의 구간에 포함되어 있어야 한다.

구간의 점수란 구간에 속한 수의 최댓값과 최솟값의 차이이다.

예를 들어, 배열이 [1, 5, 4, 6, 2, 1, 3, 7] 이고, M = 3인 경우가 있다.

이때, [1, 5], [4, 6, 2], [1, 3, 7]로 구간을 나누면 각 구간의 점수는 4, 4, 6점이 된다. 이때, 최댓값은 6점이다.

만약, [1, 5, 4], [6, 2, 1], [3, 7]로 구간을 나누었다면, 각 구간의 점수는 4, 5, 4점이 되고, 이때 최댓값은 5점이 된다.

두 경우 중에서 최댓값이 최소인 것은 5점인 것이고, 5점보다 최댓값을 작게 만드는 방법은 없다.

배열과 M이 주어졌을 때, 구간의 점수의 최댓값의 최솟값을 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N)

둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수이다.

▸ 출력

첫째 줄에 구간의 점수의 최댓값의 최솟값을 출력한다.

 

문제 풀이  

최적화 문제를 결정 문제로 바꿔서 푸는 파라메트릭 서치 문제이다.  M개 이하의 구간을 나눠서 각 구간 점수(구간 최댓값 - 구간 최솟값)의 최소를 구하면 된다.

• 최적화 문제: 0~N의 배열을 모두 방문해서 각 구간 점수를 구하여 최솟값을 반환한다.
• 결정 문제: 0~N의 배열을 모두 방문해서 구간 점수가 mid보다 큰 값을 포함한 구간 집합의 수가 m보다 큰지 여부를 반환한다.

 

최적화 문제로 풀면 구간을 나눌 수 있는 경우의 수를 모두 고려해야 하지만 결정 문제로 바꾸면 구간 점수가 최소든 아니든 간에 mid보다 큰 구간이 있는지만 확인해주면 된다.

 

해당 배열에서 mid값 보다 큰 값이 포함된 구간 집합의 크기가 m보다 큰지 조사하기

1. mid값을 메서드 인자로 넣어준다.
2. 0부터 시작하여 구간 점수(max-min)가 mid보다 넘게 되는지 조사한다.
   1. mid보다 크면 해당 인덱스에서 구간을 자르고 max, min값을 다. cnt++;
   2. 주의해야 할 점은 구간은 하나 이상의 연속된 수로 1개만 포함될 수 도 있다. 따라서 i--;로 해당 구간을 한 번 더 조사해준다.
3. 그렇게 구한 구간의 수를 반환한다.

static int solve(int mid) {
	int cnt = 1;
	int min = INF;
	int max = -INF;
	for(int i=0; i<n; i++) {
		min = Math.min(min, arr[i]);
		max = Math.max(max, arr[i]);
		if(max - min > mid) {
			cnt++;
			max = -INF; min = INF;
			i--;
		}
	}
	return cnt; // mid보다 큰 최댓값이 포함된 구간의 수
}

 

파라메트릭 서치

1. 배열의 최솟값과 최댓값을 사이에 두고 파라메트릭 서치를 동작시킨다. 
2. int mid = (left + right)/2;
   1. mid값을 위에서 만든 메서드를 전달시킨다.
   2. 구간의 수가 m이하이면 right값을 감소시켜주고, m보다 크다면 left값을 증가시켜준다.
3. 그렇게 구한 right 값을 출력해주면 된다.

while(left < right) {
	int mid = (left + right)/2;
	if(solve(mid)<=m) {
		right = mid;
	}else {
		left = mid+1;
	}
}

 

풀이 코드 

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

public class Main {

	static int n, INF = 987654321;
	static int[] arr;
	public static void main(String[] args) throws  IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		int left = 0;
		int right = -1;
		arr = new int[n];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			right = Math.max(right, arr[i]);
		}
		
		while(left < right) {
			int mid = (left + right)/2;
			if(solve(mid) <= m) {
				right = mid;
			}else {
				left = mid+1;
			}
		}
		System.out.println(right);
	}
	
	static int solve(int mid) {
		int cnt = 1;
		int min = INF;
		int max = -INF;
		for(int i=0; i<n; i++) {
			min = Math.min(min, arr[i]);
			max = Math.max(max, arr[i]);
			if(max - min > mid) {
				cnt++;
				max = -INF; min = INF;
				i--;
			}
		}
		return cnt;
	}
}