고무줄이 주어진다. 고무줄의 둘레는 $n$이며 $m$개의 홈이 파져있다.
고무줄을 잘라 $k$겹의 고무줄 중 가장 작은 고무줄의 길이를 최대화하는 문제이다.
순수 greedy만 생각을 했었는데 이분탐색으로 원의 기준을 돌리면서 $O(m^2 log n)$에 해결할 수 있다.
원의 기준을 돌리면서 arr배열에 다시 넣었는데 배열 크기를 2$m$으로 잡고 idx값만 바꾸면서 돌려줄 수 있다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n, m, k;
int arr[MAXN];
int sub[MAXN];
bool ispossible(int mid) { // 모든 part >= mid인지 판별
for (int i = 0; i < m; i++) {
int t = 0;
int idx = 0;
for (int j = i; j < m; j++) arr[idx++] = sub[j];
for (int j = 0; j < i; j++) arr[idx++] = sub[j];
int here = 0;
for (int j = 0; j < m; j++) {
if (here < mid) here += arr[j];
if (here >= mid) {
here = 0;
t++;
}
}
if (here >= mid) t++;
if (t >= k) return true;
}
return false;
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < m; i++) scanf("%d", &arr[i]);
for (int i = 0; i < m - 1; i++) sub[i] = arr[i + 1] - arr[i]; sub[m - 1] = n - arr[m - 1] + arr[0];
int l = 1, r = n;
while (l <= r) {
int mid = (l + r) >> 1;
if (ispossible(mid)) l = mid + 1;
else r = mid - 1;
}
printf("%d\n", r);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기