문제
풀이
1차 시도: 완전탐색인줄
N 범위를 안 보고 완전탐색 + DFS로 풀었더니 당연히 시간초과가 떴다ㅎㅎ;; 제발 문제 조건좀 똑바로 읽자!
import java.io.*;
public class Q13397 {
private static BufferedReader br;
private static BufferedWriter bw;
private static int N;
private static int M;
private static int[] arr;
private static int minScoreOnBlockCount = Integer.MAX_VALUE;
private static int answer = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
parseInputAndInitParams();
findAnswer();
bw.append(Integer.toString(answer));
br.close();
bw.close();
}
private static void parseInputAndInitParams() throws IOException {
String[] line = br.readLine().split(" ");
N = Integer.parseInt(line[0]);
M = Integer.parseInt(line[1]);
arr = new int[N];
line = br.readLine().split(" ");
for (int i = 0; i < N; i++)
arr[i] = Integer.parseInt(line[i]);
}
private static void findAnswer() {
for (int blockCount = M; blockCount >= 1; blockCount--) {
calcMaximumScoreOnBlockCount(blockCount);
answer = Math.min(answer, minScoreOnBlockCount);
}
}
private static void calcMaximumScoreOnBlockCount(int blockCount) {
dfs(new int[blockCount - 1], new boolean[arr.length], 0, 0, blockCount - 1);
}
private static void dfs(int[] indexes, boolean[] visited, int start, int depth, int targetDepth) {
if (depth == targetDepth) {
minScoreOnBlockCount = Math.min(minScoreOnBlockCount,
calcMaxScoreOfBlocks(indexes));
return;
}
for (int i = start; i < N - 1; i++) {
if (!visited[i]) {
visited[i] = true;
indexes[depth] = i;
dfs(indexes, visited, start + 1, depth + 1, targetDepth);
visited[i] = false;
indexes[depth] = -1;
}
}
}
private static int calcMaxScoreOfBlocks(int[] indexes) {
int result = Integer.MIN_VALUE;
if (indexes.length == 0) {
result = calcScoreOfBlock(0, arr.length - 1);
} else {
result = Math.max(result, calcScoreOfBlock(0, indexes[0]));
for (int i = 0; i < indexes.length - 1; i++)
result = Math.max(result, calcScoreOfBlock(indexes[i] + 1, indexes[i + 1]));
result = Math.max(result, calcScoreOfBlock(indexes[indexes.length - 1] + 1, arr.length - 1));
}
return result;
}
private static int calcScoreOfBlock(int startIndex, int endIndex) {
int maximum = Integer.MIN_VALUE, minimum = Integer.MAX_VALUE;
for (int i = startIndex; i <= endIndex; i++) {
maximum = Math.max(maximum, arr[i]);
minimum = Math.min(minimum, arr[i]);
}
return maximum - minimum;
}
}2차 시도: 이분탐색 적용
이분탐색을 대체 어떻게 적용하는지 생각이 잘 떠오르지 않아서 결국 검색을 했다. 자괴감들고 힘들어...
아무튼 이 문제의 풀이과정은 다음과 같다.
maxScoreOfBlocks를 기준으로 이분탐색을 진행한다.
- 최솟값
left는 block의 원소가 한 개일 때,0이다.- 최댓값
right는arr의 최댓값 - 1이다.mid값을 만들기 위해arr의 원소들을 몇 개의 block으로 나눠야 하는지blockCount를 센다.
a. 만약blockCount <= M이면,maxScoreOfBlocks를 감소시켜 다시 탐색한다.
b.blockCount > M이면,maxScoreOfBlocks를 증가시켜 다시 탐색한다.
아이디어는 검색해서 참고하고, 코드는 보지 않고 내가 직접 구현했는데, 생각보다 쉽게 바로 구현에 성공해서 더 아쉬웠다. blockCount를 먼저 제공하고 maxScore을 구하는 방식으로만 머리가 돌아갔는데, 그 반대로 생각을 하지 못해서 문제를 푸는 데에 실패한 것 같다.
제발!!!! 생각을! 열심히! 하고! 문제를! 잘! 풀자!!!!
import java.io.*;
import java.util.Arrays;
public class Main {
private static BufferedReader br;
private static BufferedWriter bw;
private static int N;
private static int M;
private static int[] arr;
private static int answer = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
parseInputAndInitParams();
findAnswer();
bw.append(Integer.toString(answer));
br.close();
bw.close();
}
private static void parseInputAndInitParams() throws IOException {
String[] line = br.readLine().split(" ");
N = Integer.parseInt(line[0]);
M = Integer.parseInt(line[1]);
arr = new int[N];
line = br.readLine().split(" ");
for (int i = 0; i < N; i++)
arr[i] = Integer.parseInt(line[i]);
}
private static void findAnswer() {
int left = 0, right = Arrays.stream(arr).max().getAsInt() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (isMaxScoreOfBlocksAvailable(mid)) {
answer = Math.min(answer, mid);
right = mid - 1;
} else {
left = mid + 1;
}
}
}
private static boolean isMaxScoreOfBlocksAvailable(int maxScore) {
int blockCount = 0;
int currentMax = Integer.MIN_VALUE, currentMin = Integer.MAX_VALUE;
for (int element : arr) {
int tmpMax = Math.max(currentMax, element);
int tmpMin = Math.min(currentMin, element);
if (tmpMax - tmpMin <= maxScore) {
currentMax = tmpMax;
currentMin = tmpMin;
} else {
blockCount++;
currentMax = element;
currentMin = element;
}
}
return blockCount + 1 <= M;
}
}