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

문제

N개의 수로 이루어진 1차원 배열이 있다. 이 배열을 M개 이하의 구간으로 나누어서 구간의 점수의 최댓값을 최소로 하려고 한다. 구간은 다음과 같은 조건을 만족해야 한다.

1. 하나의 구간은 하나 이상의 연속된 수들로 이루어져 있다.
2. 배열의 각 수는 모두 하나의 구간에 포함되어 있어야 한다.

구간의 점수란 구간에 속한 수의 최댓값과 최솟값의 차이이다.

예를 들어, 배열이 [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보다 작거나 같은 자연수이다.

출력

첫째 줄에 구간의 점수의 최댓값의 최솟값을 출력한다.

예제 입력 1

8 3
1 5 4 6 2 1 3 7

예제 출력 1

5

예제 입력 2

4 2
1 1 1 1

예제 출력 2

0

예제 입력 3

7 4
1 2 3 1 2 3 1

예제 출력 3

2

예제 입력 4

5 1
1 100 99 2 3

제출답안

• 조합으로 풀었다가 메모리 초과를 받고 다시 생각해야 했다.
• 어떻게 구간을 나눠야 m개 혹은 m개 이하를 맞추고 최대값을 찾을 수 있을까? 를 고민했지만 결국 해결하지 못하고 구글링을 하였다.
• 답안 출처

1. 이분탐색을 통하여 값을 갱신할것이기 때문에 왼쪽 값과 오른쪽 값을 설정한다.
2. 왼쪽 값이 오른쪽 값보다 작거나 같을 때 까지 while을 돈다.
3. 이 때 이분탐색 기준을 중앙값으로 두고 비교한다.
   1. 이 값이 최솟값이 되어 구간을 자르는 기준이 된다.
   2. 그러면 구간을 나누었을 때 그 구간들의 최댓값 - 최솟값이 mid가 되고 이것을 기존 값과 비교하면 된다.
4. 배열과 중앙값, m을 넣고 확인한다.
   1. 최솟값과 최댓값을 설정하고 현재 구간의 개수를 선언한다.
   2. 배열만큼 for loop를 돈다.
   3. 만약 최댓값이 현재의 수보다 작으면 최댓값을 i로 갱신한다.
   4. 최솟값이 현재의 수보다 크면 최솟값을 i로 갱신한다.
   5. 최댓값 - 최솟값이 중앙값보다 크다면 구간을 자르고 (divide를 1 증가) 최솟값과 최댓값도 i로 설정한다.
   6. 나눈 구간의 개수가 m보다 작거나 같은지 확인한다.
5. 구간을 나눌 수 있으면 범위를 줄여서 다시 탐색한다.
6. 구간을 나눌 수 없으면 범위를 늘려서 다시 탐색한다.

import sys

input = sys.stdin.readline

def isValid(arr, mid, m):
    # (4-1)
    low = arr[0]
    high = arr[0]
    divide = 1

    # (4-2)
    for i in arr:
        # (4-3)
        if high < i:
            high = i
        # (4-4)
        if low > i:
            low = i
        # (4-5)
        if high - low > mid:
            divide += 1
            low = i
            high = i
    # (4-6)
    return m >= divide


def solution():
    n, m = map(int, input().split())
    arr = list(map(int, input().split()))
    # (1)
    right = max(arr)
    left = 0
    result = right
    # (2)
    while left <= right:
        # (3)
        mid = (left + right) // 2
        # (4)
        if isValid(arr, mid, m):
            # (5)
            right = mid - 1
            result = min(result, mid)
        # (6)
        else:
            left = mid + 1
    print(result)


solution()