💡 문제
N개의 수로 이루어진 1차원 배열이 있다. 이 배열을 M개 이하의 구간으로 나누어서 구간의 점수의 최댓값을 최소로 하려고 한다. 구간은 다음과 같은 조건을 만족해야 한다.
- 하나의 구간은 하나 이상의 연속된 수들로 이루어져 있다.
- 배열의 각 수는 모두 하나의 구간에 포함되어 있어야 한다.
구간의 점수란 구간에 속한 수의 최댓값과 최솟값의 차이이다.
예를 들어, 배열이 [1, 5, 4, 6, 2, 1, 3, 7] 이고, M = 3인 경우가 있다.
이때, [1, 5], [4, 6, 2], [1, 3, 7]로 구간을 나누면 각 구간의 점수는 4, 4, 6점이 된다. 이때, 최댓값은 6점이다.
만약, [1, 5, 4], [6, 2, 1], [3, 7]로 구간을 나누었다면, 각 구간의 점수는 4, 5, 4점이 되고, 이때 최댓값은 5점이 된다.
두 경우 중에서 최댓값이 최소인 것은 5점인 것이고, 5점보다 최댓값을 작게 만드는 방법은 없다.
배열과 M이 주어졌을 때, 구간의 점수의 최댓값의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N)
둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 구간의 점수의 최댓값의 최솟값을 출력한다.
💭 접근
이 문제는 이분 탐색을 활용한 매개 변수 탐색 문제로, 구간의 점수의 최대값의 최솟값을 임의로 설정하고, 이 값에 따라 구간을 m개 나눌 수 있는지를 판단하는 문제이다.
따라서 변수는 다음과 같이 설정했다.
start: 구간의 점수의 최소값(0보다 작아질 순 없다) →0
end: 구간의 점수의 최대값 →max(num) - min(num)
mid: 구간을 나눌 실제 점수의 최대값의 최솟값 →(start + end) // 2
변수를 위처럼 설정하고, mid값을 조절하며 이 mid값에 따라 구간을 m개 나눌 수 있는 mid값을 찾으면 된다.
따라서 mid보다 구간의 점수가 커지지 않도록 구간을 나눈 뒤, 구간의 개수가 m보다 적거나 같다면 구간의 최대값의 최솟값을 더 줄일 수 있는 여지가 있기 때문에 mid를 줄인다.
반대로, mid보다 구간의 점수가 커지지 않도록 구간을 나눈 뒤, 구간의 개수가 m보다 많다면 구간의 최대값의 최솟값을 늘려 구간의 개수를 줄여야 하므로 mid를 늘린다.
📒 코드
def binary_search():
start = 0
end = max(num) - min(num)
ans = 0
while start <= end:
mid = (start + end) // 2
cnt = binning(mid)
if cnt <= m:
ans = mid
end = mid - 1
else:
start = mid + 1
return ans
def binning(min_num):
cnt = 0
start_idx = 0
end_idx = 1
while start_idx + end_idx <= n:
tmp_max = max(num[start_idx:start_idx + end_idx])
tmp_min = min(num[start_idx:start_idx + end_idx])
if tmp_max - tmp_min > min_num:
cnt += 1
start_idx = start_idx + end_idx - 1
end_idx = 1
else:
end_idx += 1
return cnt + 1
n, m = map(int, input().split())
num = list(map(int, input().split()))
print(binary_search())💭 후기
계속해서 비슷한 유형의 문제를 풀고 있어 많이 익숙해진 것같다.
🔗 문제 출처
https://www.acmicpc.net/problem/13397
