[Python/파이썬] 백준 13397번 구간 나누기 2

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

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = list(map(int, input().split()))


def count_section(target):
    max_value = min_value = arr[0]
    cnt = 1
    for i in range(1, n):
        if max_value < arr[i]:
            max_value = arr[i]
        if min_value > arr[i]:
            min_value = arr[i]
        if max_value - min_value > target:
            cnt += 1
            max_value = min_value = arr[i]
    return cnt


def binary_search(sections):
    l, r = 0, 10000
    answer = 0
    while l <= r:
        mid = (r+l)//2
        if count_section(mid) <= sections:
            r = mid-1
            answer = mid
        else:
            l = mid+1
    return answer


print(binary_search(m))

 

`count_section()`

파라미터로 받은 target이 구간의 점수의 최댓값이 되는 경우에 구간을 몇 개로 나눌 수 있는지 구하는 함수이다. 

 

`binary_search()`

이름 그대로 이분탐색을 하기 위한 함수이다. 이때 이분탐색은 구간의 점수의 최댓값의 최솟값을 찾기 위해 진행된다.

이분탐색 과정에서 mid는 구간의 점수의 최댓값이라고 생각하면 된다. `count_section(mid)`를 실행한 결괏값이 M보다 작거나 같다면 가능한 경우이므로 이 경우에는 answer에 mid값을 저장하고, 더 작은 값이 가능한지 탐색하러 가면 된다.