BOJ :: [13397] 구간 나누기 2

문제

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

13397번: 구간 나누기 2

 

문제 설명

구간 나누기 나눌 구간 k와 숫자로 구성된 배열이 주어진다. 주어진 배열에서 k개의 구간으로 나누어 각 구간의 최댓값과 최솟값의 차이를 구해 각 구간의 값 중 최댓값이 최솟값이 되는 경우를 찾는 문제이다. 

문제에서 주어진 예제 1번은 아래 그림과 같이 구간을 나누었다고 가정해 보자.

 

구간 예제 1

구간 예제 2

위 그림에서 2번째 줄은 주어진 배열이며, 3번째 줄은 나누어진 구간에서 (최댓값 - 최솟값)을 한 결과이다. 구간 예제 1과 같이 구간을 나누는 경우 최댓값이 6이지만 구간 예제 2와 같이 구간을 나누는 경우 최댓값이 5이므로 위 구간 예제 1, 2의 최댓값 중에서 최솟값은 예제 2번의 5가 된다.

 

풀이

이 문제는 이분 탐색으로 해결할 수 있다. 이 문제의 핵심은 구간을 나눌 기준 값을 변경해 가면서 나눌 구간을 찾는다는 것이다. 즉, 기준 값을 증가시키거나 감소시키면서 구간을 만들어 주는데 이 기준 값을 이분 탐색으로 구한다.

먼저 left를 0으로, 주어진 배열에서 가장 큰 수를 right로, mid를 (left + right)/2로 지정한다. 그리고 주어진 배열 첫 번째부터 마지막까지 탐색하면서 현재까지의 (최댓값 - 최솟값)이 mid보다 큰 경우 이전 인덱스까지를 한 구간으로 하며 배열이 끝날 때까지 반복하여 생기는 구간의 수를 구한다. 그리고 계산한 구간의 수가 주어진 구간 k보다 작거나 같으면 기준 값인 mid를 줄이고 구간 k보다 크면 기준 값인 mid를 늘려 구간의 수를 조절한다. 구간의 수가 주어진 k보다 크거나 같을 경우 기준값인 mid값을 비교하여 현재 저장된 최댓값과 mid를 비교하여 최댓값을 저장한다.

 

코드

import sys
input = sys.stdin.readline

def isValid(midValue):
    global result
    low = arr[0]
    high = arr[0]
    d = 1

    for i in arr:
        if high < i:
            high = i

        if low > i:
            low = i
        
        if high - low > midValue:
            d += 1
            low = i
            high = i

    return m >= d

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

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

r = max(arr)
l = 0

result = r
while l <= r:
    mid = (l + r) // 2

    if isValid(mid):
        r = mid - 1
        result = min(result, mid)
    else:
        l = mid + 1

print(result)

 

작성한 글에 잘못된 부분이나 문제가 있는 경우 댓글에 작성해 주시면 수정하도록 하겠습니다 . 질문도 환영합니다! :)