[BOJ/백준] 13397 구간 나누기 2

import sys

def input():
    return sys.stdin.readline().rstrip()


def check(mid):
    idx = 0
    temp = []
    cnt = 0
    while idx<N:
        if cnt >M:
            return False
        if temp:
            min_value,max_value = min(temp),max(temp)
            if abs(arr[idx]-min_value)>mid or abs(arr[idx]-max_value)>mid:
                cnt += 1
                temp = [arr[idx]]
            else:
                temp.append(arr[idx])
        else:
            temp.append(arr[idx])
        idx += 1
    if temp:
        cnt += 1
    if cnt>M:
        return False
    return True
        

N,M = map(int,input().split())

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


left = -1
right = 10001
while left+1<right:
    mid = (left+right)//2

    if check(mid):
        right = mid
    else:
        left = mid

print(right)

이 문제는 구간의 최대값과 최소값을 비교한 값이 최대가 되어야하고 M개 이하의 그룹으로 나뉘어야한다.

 

이 문제를 푸는 법은 이분탐색을 이용해서 풀면된다. 이분탐색의 탐색근거가 되는 값은 최대-최소의 값이다.

 

이 값이 벗어나는 경우 새로운 그룹을 만들어주고, 총 그룹의 수가 M개 초과가 되면 False를 만족하면 True로 하면서

 

True를 만족 최소의 값을 구하면 된다.

 

위의 풀이는 list에 계속 넣다 빼다보니 시간이 좀 오래걸린다.

 

 

import sys

def input():
    return sys.stdin.readline().rstrip()


def check(mid):
    min_value = arr[0]
    max_value = arr[0]
    idx = 1
    cnt = 1
    while idx<N:
        if cnt>M:
            return False
        if min_value>arr[idx]:
            min_value = arr[idx]
        if max_value < arr[idx]:
            max_value = arr[idx]
        
        if max_value-min_value>mid:
            min_value = arr[idx]
            max_value = arr[idx]
            cnt += 1
        idx += 1
    if cnt>M:
        return False
    else:
        return True
        

N,M = map(int,input().split())

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


left = -1
right = 10001
while left+1<right:
    mid = (left+right)//2

    if check(mid):
        right = mid
    else:
        left = mid

print(right)

똑같은 원리지만, 훨씬 빠른 풀이다. 리스트를 저장하는게 아니라, 최소 최대값을 계속 갱신을 해주면서,

 

그 값이 주어진 mid보다 크면, 최소 최대값을 현재 탐색중인 값으로 초기화 해준뒤 cnt를 늘려주면 된다.

 

이 풀이가 좀 더 깔끔한 풀이라 생각한다.