문제 링크
문제
N개의 수로 이루어진 1차원 배열이 있다. 이 배열을 M개 이하의 구간으로 나누어서 구간의 점수의 최댓값을 최소로 하려고 한다. 구간은 다음과 같은 조건을 만족해야 한다.
- 하나의 구간은 하나 이상의 연속된 수들로 이루어져 있다.
- 배열의 각 수는 모두 하나의 구간에 포함되어 있어야 한다.
구간의 점수란 구간에 속한 수의 최댓값과 최솟값의 차이이다.
예를 들어, 배열이 [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보다 작거나 같은 자연수이다.
출력
첫째 줄에 구간의 점수의 최댓값의 최솟값을 출력한다.
알고리즘: 이분 탐색
풀이
구간의 점수의 최댓값을 최소로 만들어야 한다.
구간의 점수를 이분 탐색으로 찾아서 해결할 수 있다.
설정한 구간의 점수를 초과하지 않는다면 리스트에 값을 무조건 포함시키는게 구간의 점수의 최댓값을 최솟값으로 만드는 방법이다. 왜냐하면 포함할 수는 다음 구간의 최댓값, 최솟값, 중간값 세 종류 중 하나인데 최댓값이라 했을 때 다음 구간을 더 작게 만들 수 있고, 최솟값 또한 더 작게 만들 수 있으며, 중간값은 스코어의 아무런 영향을 끼치지 않는다. 그렇기 때문에 일관성 있게 초과하지 않는다면 무조건 리스트에 넣어주는 방식으로 진행한다.
반대로 초과하는 값이라면 cout += 1 해주고 리스트를 초기화 시켜주면됨
마지막 수까지 탐색을 완료했다면 cout 값으로 min을 업데이트할 것인지 max를 업데이트할 것인지 판단해주는데 cout<=M이라면 구간의 점수를 더 작게 만드는 방향으로 max = mid-1
cout>M이라면 구간의 점수를 더 크게 만드는 방향으로 min = mid + 1로 업데이트해 주면 된다.
ex)
5 2
1 100 99 2 3
cout = 1
첫 번째 시도 min = 0, max = 99 -> mid = 49
list에 1을 넣으면 {1} score은 0 0<=49 ture
list에 100을 넣으면 {1,100} score은 99 99<=49 false
cout+=1 {100}
list에 99를 넣으면 {100,99} score은 1 1<=49 true
list에 2를 넣으면 {100,99,2} score은 98 98<=49 false
cout += 1
cout는 현재 3이고 M은 2이기 때문에 min = mid + 1로 업데이트
두 번째 시도 min = 50, max = 99 -> mid = 74
list에 1 {1} score 0 true
list에 100 {1,100} score 99 false
cout +=1 {100}
.....
...
cout 3 M은 2이기 때문에 min = mid + 1로 업데이트
세 번째 시도 min = 75, max= 99 -> mid = 87
..
...
....
cout 3 M은 2이기 때문에 min = mid + 1로 업데이트
네 번째 시도 min = 88, max= 99 -> mid = 96
..
...
....
min = mid + 1로 업데이트
다섯 번째 시도 min = 97, max = 99 -> mid = 98
list에 1 {1} score 0 ture
list에 100 {1,100}s score 99 false
cout += 1 {100}
list에 99 true {100,99}
list에 2 true {100, 99, 2}
list에 3 true {100, 99, 2, 3}
cout = 2 cout <= M이기 때문에 max = min - 1로 업데이트
여섯 번째 시도 min = 97, max = 97 -> mid = 97
..
...
....
min = mid + 1로 업데이트
min = 98, max 97이기 때문에 min>max 탐색 종료
구간의 최대값의 최솟값은 98이 됨
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int N,M;
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());
M = Integer.parseInt(st.nextToken());
arr = new int[N];
StringTokenizer n_st = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++) {
arr[i] = Integer.parseInt(n_st.nextToken());
}
//이분 탐색
int min = 0;
int max = 9999;
while(min<=max) {
int mid = (min + max)/2;
int cout = 1;
ArrayList<Integer> section = new ArrayList<>();
for(int i=0; i<N; i++) {
section.add(arr[i]);
int score = cal_score(section);
if(score > mid) {
section = new ArrayList<>(Arrays.asList(arr[i]));
cout += 1;
}
}
if(cout<=M) max = mid - 1;
else min = mid + 1;
}
System.out.println(max+1);
}
static int cal_score(ArrayList<Integer> sec) {
int max_score = Collections.max(sec);
int min_score = Collections.min(sec);
return max_score - min_score;
}
}