[BOJ: 13397] - Python / 파이썬 - 구간 나누기 2

문제

• https://www.acmicpc.net/problem/13397

시간 복잡도

• 두 수 차의 최댓값은 k, 배열의 크기가 n -> $O(n log k)$
• 두 수 차의 최댓값은 9,999이고, 배열 크기의 최댓값은 5,000이므로 시간은 충분하다.

문제 접근법

문제의 풀이가 너무 이해가 안가서 아주 자세하게 알아보았습니다.

• 이분탐색의 시작값(start)은 모든 수가 같다는 가정 하에 0이다.

• 이분탐색의 끝값(end)은 배열의 최댓값에서 최솟값을 뺀 값이다.
  (구간의 차이가 가장 큰 값을 이분탐색의 끝값으로 시작한다.)

• 이분탐색을 통해 중간값(mid)를 구한다.

• 중간값은 구간의 점수의 최댓값-최솟값을 한 것 중 최댓값의 마지노선이다.

• 이 중간값이 최적의 값인지를 계산하는 함수(is_valid())를 실행한다.

  • 해당 함수는 새로운 중간값(mid)으로 새로운 구간들을 구한다.
  • 현재 중간값으로 구하는 구간들의 최소(min_num)와 최대(max_num)를 초기화한다.
  • 수를 차례대로 탐색하면서 구간을 구하기 때문에, 구간의 개수(count)를 1로 초기화한다.
  • 수를 차례대로 탐색한다.
    • 최댓값과 최솟값을 계속 비교하며 갱신한다.
    • 현재 구간의 최댓값에서 최솟값을 뺐을 때, 그 값이 중간값보다 크면 새로운 구간을 만들어야 한다.
    • 새로운 구간을 만들면 구간의 개수(count)가 증가하기 때문에 count + 1을 한다.
    • 또한, 새로운 구간이 현재 수(num)부터 시작되기 때문에 최솟값(min_num)과 최댓값(max_num)을 현재 수로 초기화 한다.
    • 구간의 개수가 m을 넘어가면 현재 중간값(mid)는 최적의 값이 아니기 때문에 False를 반환한다.
    • 모든 수를 탐색한 후, 구간의 개수가 m 이하면 True를 반환한다.

• 현재 중간값(mid)이 최적의 값(is_valid() == True)인 경우, 현재 중간값을 결과값(ans)에 저장하고 끝값(end)을 mid - 1로 변경한다.
  (현재 중간값으로 m개 이하의 수를 만드는 것이 가능해도, 그 이하에서 최적화된 수가 나올 수 있기 때문)

• 최적의 값이 아닌(is_valid() == False) 경우, 구간이 m개보다 많다는 뜻이기 때문에 시작값(start)을 mid + 1로 변경한다.

• 즉, is_valid()가 True라는 뜻은 현재의 중간값(mid)으로 m개 이하의 구간이 생기기 때문에, 중간값(mid)는 적정한 값이다.
  -> 이 중간값(mid) 중 최솟값을 구하는 것이 문제의 요구사항이다.
  -> 중간값(mid)을 줄이고 다시 구간나누기 실행

• is_valid()가 Flase라는 뜻은 현재의 중간값(mid)으로 m개 초과의 구간이 생기기 때문에, 중간값(mid)이 너무 작다는 뜻이다.
  -> 한 구간의 최댓값 - 최솟값의 마지노선이 작아 구간이 많이 생긴다.
  -> 중간값(mid) 증가

코드

# BOJ
# G4 - 13397(구간 나누기 2)

import sys
input = sys.stdin.readline    

n, m = map(int, input().split())
nums = list(map(int, input().split()))
start, end = 0, max(nums) - min(nums)
ans = 0

def is_valid(mid):
    min_num = max_num = nums[0]
    cnt = 1
    
    for num in nums:
        min_num = min(min_num, num)
        max_num = max(max_num, num)
        if max_num - min_num > mid:
            cnt += 1
            min_num = max_num = num
            if cnt > m:
                return False
    
    return True
    
while start <= end:
    mid = (start + end) // 2
    
    if is_valid(mid):
        ans = mid
        end = mid - 1
    else:
        start = mid + 1

print(ans)