BOJ 10919 - 선물상자
참고 링크를 보면 자세히 설명이 되어있다.
직선이라면
이 문제는 BOJ 1461 - 도서관 문제를 원형에서 하는 문제이다.
1461의 해답은 항상 가장 먼 지점부터 $K$ 개씩 갖다주어서 최적을 만든다는 것인데, DP식을 잘 정의하면 $i$ 번째 사람까지 모두 가져다주기 위해 얼마나 시간이 필요한지를 계산할 수 있다.
이 문제가 원형이 아닌 직선이라고 하자.
$dp[i]=i$ 번째 사람까지 모두 가져다주는데 최소 시간이라고 한다면
와 같이 정의가 되어 $O(n)$ 에 채워줄 수 있다.
원형에서의 풀이
원형이니까 이러한 배열을 오른쪽으로도, 왼쪽으로도 한바퀴씩 돌려 구해두자.
$\dfrac{L}{2}$ 지점을 고려하면 그것보다 왼쪽에 있는건 왼쪽에서 가져다주고 왼쪽으로 다시 $0$ 으로 가는것이 빠를 것이고
반대인 오른쪽도 유사하다.
그러나 어느 경우 왼쪽 오른쪽만 쓰는게 아닌 한바퀴를 빙 돌아 나눠주고 오는 경우가 빠른 경우가 있을 수 있고 이러한 움직임은 최대 $1$번 필요하다.
이동거리 $L$ 을 소모해 $K$ 명에게 나눠줄 수 있는데, 두 번 이상 이러한 움직임을 시행 시 $2L$을 소모해 $2K$에게 나눠주는 것이 왼쪽 $2 \cdot \left\lceil \dfrac{L}{2} \right\rceil$ 를 소모해 $K$ 를 나눠주는 것이나 오른쪽 $2 \cdot \left\lfloor \dfrac{L}{2} \right\rfloor$ 를 소모해 $K$ 를 나눠주는 것으로 올바르게 대체될 수 있기 때문이다.
따라서 만든 DP 배열을 가지고 한바퀴를 돌 때와 안돌때 모두 최소값을 구해줄 수 있다.
안 돌때는 그냥 $dp_l[i]+dp_r[i+1]$ 를 모두 검사해주면 되고,
돌 때는 좀 더 생각해봐야 한다.
돌 때 우리가 $K$ 명에게 나눠 줄 것이고 $0$ 번에서 최대한 먼 $\dfrac{L}{2}$ 지점 근처에서 연속된 사람들에게 나눠주는게 최적일 것이다.
그럼 $K$ 번 왼쪽 $0$명, 오른쪽 $K$명 $\to$ 왼쪽 $K$명 오른쪽 $0$ 명
이런식으로 모두 줘가며 검사하면 된다.
void solve() {
int n, k, l;
cin >> n >> k >> l;
vi p;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
p.pb(x);
}
vi dpL(n), dpR(n);
for (int i = 0; i < n; i++) {
if (i - k < 0) dpL[i] = p[i] * 2;
else dpL[i] = dpL[i - k] + p[i] * 2;
}
for (int i = n - 1; i >= 0; i--) {
if (i + k >= n) dpR[i] = (l - p[i]) * 2;
else dpR[i] = dpR[i + k] + (l - p[i]) * 2;
}
// 오른쪽의 시작
int s = ubi(p, l / 2);
int tot_left = s;
int tot_right = n - tot_left;
int ans = 2e18;
for (int i = -1; i < n; i++) mina(ans, (i < 0 ? 0 : dpL[i]) + (i + 1 < n ? dpR[i + 1] : 0));
if (n <= k) mina(ans, l);
else {
for (int left = k; left >= 0; left--) {
int right = k - left;
int left_val = left >= tot_left ? 0 : dpL[s - 1 - left];
int right_val = right >= tot_right ? 0 : dpR[s + right];
mina(ans, left_val + l + right_val);
}
}
cout << ans;
}
Comments