백준 13397번(파이썬):구간 나누기 2
백준 13397번 문제 정리글 입니다.
문제 출처-https://www.acmicpc.net/problem/13397
문제 내용
나의 풀이
n,m=map(int,input().split())
num=list(map(int,input().split()))
start,end=0,max(num)-min(num)
res=1e9
while start<=end:
mid=(start+end)//2
score=0
count=1
queue=[]
for i in num:
queue.append(i)
score=max(queue)-min(queue)
if score>mid:
count+=1
queue=[i]
if count>m:
break
if count<=m:
end=mid-1
res=min(res,mid)
else:
start=mid+1
print(res)
우선 이분 탐색을 이용하여 해결하기 위해
start=0, end=max(num)-min(num)으로 설정했다.그 후, 배열의 앞쪽부터 차례대로 추가해가며 구간의 점수와 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)
참조 코드
시간이 조금 오래걸려서 다른 풀이를 참고해봤다..
다른 풀이들도 나와 유사한 방법으로 했다. 다만, 구간을 정하며 탐색할 때, 두개의 포인터를 이용해서 추가해나갔다… 또한, end값을 그냥 배열에서 가장 큰 값으로 설정했다.
구간 탐색은 두개의 포인터를 이용하는 방법이 더욱 좋아보인다.
해결한 후
방법이 맞을까 고민하지말고 해결책이 나오면 바로바로 시도해보는것이 좋다…
