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를 늘려주면 된다.
이 풀이가 좀 더 깔끔한 풀이라 생각한다.
'알고리즘 > 백준' 카테고리의 다른 글
| [BOJ/백준] 16437 양 구출 작전 (0) | 2021.07.12 |
|---|---|
| [BOJ/백준] 13711 LCS 4 (0) | 2021.07.12 |
| [BOJ/백준] 4358 생태학 (0) | 2021.07.12 |
| [BOJ/백준] 16947 서울 지하철 2호선 (0) | 2021.07.12 |
| [BOJ/백준] 16472 고냥이 (0) | 2021.06.29 |