Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 돌 무더기를 병합하는 최소 비용 구하기

N개의 돌 무더기가 일렬로 놓여 있다고 가정해 봅시다. i번째 무더기에는 stones[i]개의 돌이 들어 있습니다. 한 번의 연산은 K개의 연속된 무더기를 하나로 합치는 것을 의미하며, 이때 발생하는 비용은 해당 K개 무더기에 들어 있는 돌의 총 개수입니다. 우리의 목표는 모든 돌 무더기를 하나로 합칠 때 드는 최소 비용을 구하는 것이며, 만약 합치는 방법이 존재하지 않는다면 -1을 반환해야 합니다.

문제 예시

입력이 [3, 2, 4, 1]이고 K = 2라고 가정하면, 출력은 20이 됩니다. 그 과정은 다음과 같습니다.

  • [3, 2, 4, 1]에서 시작합니다.
  • [3, 2]를 합치면 비용 5가 발생하고, 남은 상태는 [5, 4, 1]입니다.
  • [4, 1]을 합치면 비용 5가 발생하고, 남은 상태는 [5, 5]입니다.
  • [5, 5]를 합치면 비용 10이 발생하고, 최종적으로 [10]이 됩니다.

따라서 총 비용은 5 + 5 + 10 = 20이며, 이것이 가능한 최솟값입니다.

풀이 접근 방법

이 문제는 구간 DP(Interval Dynamic Programming)와 누적 합(Prefix Sum)을 활용하여 해결할 수 있습니다. 단계별로 살펴보겠습니다.

  1. n := stones 배열의 크기로 설정합니다.
  2. (n - 1) mod (k - 1)의 값이 0이 아니라면, 모든 돌을 하나로 합치는 것이 불가능하므로 -1을 반환합니다. 각 연산마다 무더기의 개수가 k - 1씩 줄어들기 때문입니다.
  3. 크기가 n + 1인 누적 합 배열 prefix를 정의합니다.
  4. i := 1부터 n까지 반복하면서 prefix[i] := prefix[i - 1] + stones[i - 1]을 계산합니다.
  5. 크기가 n × n인 2차원 dp 배열을 정의합니다.
  6. length := k부터 n까지 구간 길이를 늘려가며 반복합니다.
    • i := 0, j := length - 1부터 시작하여 j < n인 동안 i와 j를 1씩 증가시키며 반복합니다.
    • dp[i, j] := 무한대(inf)로 초기화합니다.
    • mid := i부터 mid < j인 동안 mid를 k - 1씩 증가시키며, dp[i, j] := min(dp[i, j], dp[i, mid] + dp[mid + 1, j])로 갱신합니다.
    • 만약 (j - i) mod (k - 1) == 0이라면, 해당 구간을 하나의 무더기로 합칠 수 있으므로 dp[i, j] := dp[i, j] + prefix[j + 1] - prefix[i]를 더해 줍니다.
  7. 최종적으로 dp[0, n - 1]을 반환합니다.

C++ 구현 코드

아래 구현 예제를 통해 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int mergeStones(vector<int>& stones, int k){
      int n = stones.size();
      if ((n - 1) % (k - 1) != 0)
      return -1;
      vector<int> prefix(n + 1);
      for (int i = 1; i <= n; i++) {
         prefix[i] = prefix[i - 1] + stones[i - 1];
      }  
      vector<vector<int>> dp(n, vector<int>(n));
      for (int length = k; length <= n; length++) {
         for (int i = 0, j = length - 1; j < n; i++, j++) {
            dp[i][j] = INT_MAX;
            for (int mid = i; mid < j; mid += k - 1) {
               dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid +
               1][j]);
            }
            if ((j - i) % (k - 1) == 0) {
               dp[i][j] += prefix[j + 1] - prefix[i];
            }
         }
      }
      return dp[0][n - 1];
   }
};
main(){
   Solution ob;
   vector<int> v = {3,2,4,1};
   cout << (ob.mergeStones(v, 2));
}

입력

{3,2,4,1}, 2

출력

20

핵심 포인트 정리

  • 병합 가능 여부 판단: (n - 1)이 (k - 1)로 나누어떨어지지 않으면 어떤 순서로도 모든 돌을 하나로 합칠 수 없으므로 -1을 반환합니다.
  • 누적 합 활용: 특정 구간의 돌 개수 합을 O(1) 시간에 구하기 위해 prefix sum 배열을 사용합니다.
  • 구간 DP: dp[i][j]는 i번째부터 j번째 무더기까지 합치는 최소 비용을 의미하며, 구간을 적절히 분할하는 mid 지점을 탐색하면서 최솟값을 찾습니다.