BOJ 13997 구간 나누기 2

n개의 수로 이루어진 수열이 주어지면, m개 이하의 그룹으로 묶는데 각 그룹은 1개 이상의 연속된 수들로 이루어져야 하고 수열의 모든 수가 그룹에 포함되어야 한다.
이 때, 각 그룹에서 최대값과 최소값의 차이가 구간의 점수인데, 각 구간의 점수들 중 최대값이 최소가 나오도록 모든 수를 다 포함하는 m개 이하의 그룹을 만들어야 하는 문제이다.
그래서 최대값 중 최소인 값을 구하는 문제이다.

일단 m개 이하의 그룹을 만들라고 되어있는데, m개 이하의 그룹으로 최대값이 최소가 된다면 m개의 그룹으로도 최대값이 최소가 될 것이다. 그러니까 그냥 m개의 그룹을 만든다고 생각하는 게 편할 것 같다.

어렵다. 하지만 정말 감사하게도 아이디어가 하나 떠올랐다.
일단 주어지는 수는 1이상 10000이하의 수들이다. 그렇다면 그룹을 만들었을 때 차이의 값으로 나올 수 있는 값은 0 ~ 9999 일 것이다. 일단 m개 이하의 그룹으로 모든 수를 묶긴해야 하는데, 직접 그룹으로 묶어본다. 어떻게 묶을 것이냐면, 일단 m개 이하의 그룹으로 만들어야 하는데, 앞에서 얼마나 묶느냐에 따라 m개를 넘어갈 수 있는데, 일단 묶을 때 개수를 최소로 되게 해야하므로 묶을 수 있는 한 최대한 많이 묶어준다. 그래야 m개 이하가 될 가능성이 커진다. 근데 묶을 때 무엇을 기준으로 최대한 많이 묶으란 말인가? 바로 그룹내의 차이값을 정해놓고 그 이하가 될 수 있는 수들은 최대한 많이 묶는 것이다. 그렇게 묶어서 그룹이 m개이하가 되면 차이값을 더 줄여서 해본다. 차이는 0~9999이고, 그룹을 묶는데는 O(N)이 걸리므로 시간 내에 충분히 들어올 수 있을 것이다.

하지만 일정한 차이값 이하를 유지하면서 그룹을 묶는 것도 문제이다. 그럼 각 그룹에서 최대값, 최소값을 기록해가면서 묶어야 하나? 그러면 될 것 같다. 아니면 정렬을 해서, 작은 값부터 그룹을 묶는 시작점으로 놓고 묶기 시작하는 것도 편할 것 같다.

그리고 모든 차이값(0 ~ 9999)에 대해 다 해볼 것이 아니라 이분 탐색으로 해보는 것이 훨씬 빠를 것이다.

구현해 봐야겠다. 구현하니 예제는 제대로 나오는데 구현이 생각보다 간단치는 않았다. 정렬후 작은 값부터 묶는 방식으로 했는데, 순서상 첫 번째 수 부터 시작하면서 각 그룹에서 최대값, 최소값을 기록해 가면서 묶는 방식으로도 구현해 봐야겠다. 구현 자체는 각 그룹에서 최대, 최소값을 기록해 가면서 묶는 방식이 더 쉬운 것 같다. 두 코드 모두 제출해서 AC를 받았다! 아... 좀 무기력해 있었는데 어떻게 풀어야할지 생각이 나다니...감사합니다. 열심히 해야겠다!