[boj] 13397_구간 나누기2_python

문제링크

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

13397번: 구간 나누기 2

---

문제설명

입력

1.  배열의 크기 N과 M이 주어진다.

2. 배열에 들어있는 수가 순서대로 주어진다. ( 0 < lst내부 수 <= 10,000)

 

출력

1. 구간의 점수의 최댓값의 최솟값을 출력

 

제한

• 1 ≤ N ≤ 5,000, 1 ≤ M ≤ N
• 하나의 구간은 하나 이상의 연속된 수들로 이루어져 있다.
• 배열의 각수는 모두 하나의 구간에 포함되어 있어야 한다.
• 구간의 점수란 구간에 속한 수의 최댓값과 최솟값의 차이이다.
• 구간의 점수의 최댓값이 최소가 되도록 한다.

---

비슷한 문제

paramertric search를 하는 다른 문제인 나무 자르기와 비슷한 문제였다. 

나무 자르기 같은 경우에는 M미터의 나무를 가져가기 위해 설정할 수 있는 절단기의 최대 높이를 지정하는 문제였다.

# https://www.acmicpc.net/problem/2805
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N, M = map(int, input().split())
_list = list(map(int, input().split()))
_list.sort()
def parametical_search(s, e):
    if s > e:
        return s-1
    cnt = 0
    mid = (s + e) // 2
    for i in range(N):
        if _list[i] >= mid:
            cnt += ( _list[i] - mid )
    if cnt >= M:
        return parametical_search(mid+1, e)
    else:
        return parametical_search(s, mid-1)
print(parametical_search(1, _list[-1]))

---

문제풀이

시간 복잡도 : scoreRange O(N) * parametric_search O( log₂ max(lst) ) => O(N log₂ max(lst) )

공간 복잡도 : lst O(N) * scoreRange O( log₂ max(lst) ) (재귀로 인한 복잡도) => O( N log₂ max(lst) ) 

 

위에서 살펴본 나무 자르기와의 차이점은 scoreRange, 즉 이러한 구간이 하나가 아닌 여러개라는 것이 있다.

parametric search에서

나무자르기 문제는 절단기 높이의 최댓값을 반환했다면

구간 나누기2 문제는 구간의 점수의 최댓값을 반환했다.

 

하지만 이러한 구간의 점수의 최댓값을 구하기 위해서는

구간의 점수라는 것을 먼저 구해야할 필요가 있었는데

그러한 구간의 점수를 설정하는데 필요했던 것이 바로 scoreRange 함수였다.

자세한 설명은 주석으로 대체한다.

import sys # 재귀 깊이 재설정, 빠른 입력, INF 지정을 위해 사용
sys.setrecursionlimit(10 ** 8)
INF = sys.maxsize
input = sys.stdin.readline
# 배열의 크기 N과 M을 지정
N, M  = map(int, input().split())
lst = list(map(int, input().split()))

# 구간의 최댓값을 탐색한다.
def parametric_search(l, r):
	# iterative_parametric_search
    while r > l:
        mid = (l+r)//2
        # recursive func : scoreRange(mid)
        # 구간의 수가 M 이하인 경우 right 값을 갱신
        if scoreRange(mid) <= M:
            r = mid
        # M 초과일 경우 l값을 갱신
        else:
            l = mid+1
    # l >= r이 될 때의 r은 구간의 최댓값을 반환한다.
    return r

# 구간의 점수를 설정하는 로직
def scoreRange(mid):
	# i : 배열의 인덱스, res : mid보다 큰 최댓값이 포함된 구간의 수
    i, res = 0, 1
    _min, _max = INF, -INF
    while i < N:
    	# 구간의 최소와 최대를 탐색
        _min, _max = min(_min, lst[i]), max(_max,lst[i])
        # _max - _min : 현재 구간의 최댓값, mid : 과거 구간의 최댓값
        # 현재가 과거보다 크면 구간을 갱신해준다.
        if _max - _min > mid:
            res += 1
            _min, _max = INF, -INF
        # 아니라면 다음으로 넘어간다.
        else: i += 1
    return res

# 0부터 lst에 들어간 값중 최댓값을 범위로 삼는다.
print(parametric_search(0, max(lst)))

 

---

참고 레퍼런스

1. https://loosie.tistory.com/638

[BOJ] 백준 13397번 구간 나누기 2 (Java)