BOJ 10919 - 선물상자

BOJ 10919 - 선물상자

참고 링크를 보면 자세히 설명이 되어있다.

직선이라면Permalink

이 문제는 BOJ 1461 - 도서관 문제를 원형에서 하는 문제이다.

1461의 해답은 항상 가장 먼 지점부터 $K$ 개씩 갖다주어서 최적을 만든다는 것인데, DP식을 잘 정의하면 $i$ 번째 사람까지 모두 가져다주기 위해 얼마나 시간이 필요한지를 계산할 수 있다.

이 문제가 원형이 아닌 직선이라고 하자.

$dp[i]=i$ 번째 사람까지 모두 가져다주는데 최소 시간이라고 한다면

와 같이 정의가 되어 $O(n)$ 에 채워줄 수 있다.

원형에서의 풀이Permalink

원형이니까 이러한 배열을 오른쪽으로도, 왼쪽으로도 한바퀴씩 돌려 구해두자.

$\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;
}

참고