1000. Minimum Cost to Merge Stones - Streak 4

비슷한 문제를 풀어본 적이 있다.
https://www.acmicpc.net/problem/11066

 

이 문제와 다른 것은 뭘까?

• 파일 합치기는 반드시 바로 옆칸 1개와 합치기 때문에, 순차대로 순회하기가 쉽다.
• 이 문제는 연속된 k칸끼리 합쳐야 하기 때문에, 추가적인 처리가 필요하다.
  • n%(k-1)==1 이 아니면 -1을 반환해야 한다.
  • 연속된 k칸끼리의 합치는 방법을 생각해야 한다.

파일 합치기의 경우

• DP[i][j] = DP[i][k] + DP[k+1][j] + psum[j] - psum[i-1]

이 문제는?

• 연속된 k칸을 합쳐야 한다.

 

점화식 자체가 달라지는건가?

• dp[i][p] + dp[p][q] + ...
• k가 커지면 for문의 깊이도 그만큼 커진다.

k가 2인 경우를 제외하고,
내부가 len % (k-1) == 1 이 되는 경우만 연산을 하면 올바른 돌무더기 합치기를 찾을 수 있다.

---

정해

f[i][j][m]을 i번 더미부터 j번 더미까지를 정확히 m개의 더미로 합치는 최소 비용으로 정의하자.
왜 세 번째 차원 m이 필요할까?
중간 상태가 중요하기 때문이다.
최종 합치기를 하기 전에 어떤 부분을 특정 개수의 더미로 먼저 만들어야 하는 경우가 무조건 생긴다.

 

다음과 같이 점화식을 세워보자.

• 구간 [i, j]를 m개의 더미로 만들기 위해, 어떤 분할점 h에서 나누고
  [i, h]를 1개의 더미로, [h+1, j]를 m-1개의 더미로 만든 뒤 결합할 수 있다.
• 구간 [i, j]를 1개의 더미로 만들고자 할 때는, 먼저 그것을 K개의 더미로 만든 다음(비용 f[i][j][K]), 그 K개를 한 번에 합치는 마지막 합치기 비용(구간 [i, j]의 돌 개수의 합)을 더한다.

즉, 일일히 k개의 묶음으로 나누는 방법을 한번에 구하지 않고,

1. m-1개의 묶음과 1개의 묶음으로 나눠 생각한 뒤
2. 이를 1개의 묶음으로 합치는 과정의 반복을 통해

1부터 n까지의 값들을 1묶음으로 합치는 문제였다.

 

초기 상태는 f[i][i][1] = 0가 된다. (더미 하나는 이미 1개이므로 비용이 없다.)

 

정답은 f[1][n][1], 즉 1번부터 n번까지 모든 돌을 정확히 1개의 더미로 합치는 최소 비용이 된다.

 

 

그럼 점화식은 어떤 형태가 될까?
k개의 묶음을 1개의 묶음으로 바꾸는 과정을, [i,j] 범위를 천천히 넓혀가며 확장/축소를 반복하면 된다.

 

이때 순회순서는 다음과 같다.

1. 묶을 길이(어디부터 어디까지): [2, n]
2. 시작점: [1, n - 묶을 길이 + 1], 끝점: 시작점 + 묶을 길이
3. 묶음 크기(몇개의 묶음으로 만들건지): [2, k] (묶음을 2개부터 만들고, 최종적으로 k개의 묶음으로 만들어야 함
4. 중간 지점 위치: [시작점, 끝점], 이때 길이 체크 필요

class Solution {
    public int mergeStones(int[] stones, int k) {
        int n = stones.length;
        if(k != 2 && !check(n, k)){
            return -1;
        }

        int[] psum = new int[n+1];
        for(int i = 0; i<n; i++){
            psum[i+1] = psum[i] + stones[i];
        }

        int[][][] dp = new int[n+1][n+1][k+1];
        for(int i = 0; i<=n; i++)
            for(int j = 0; j<=n; j++)
                Arrays.fill(dp[i][j], Integer.MAX_VALUE/2);
        for(int i = 1; i<= n; i++){
            dp[i][i][1] = 0;
        }

        for(int length = 2; length <= n; length++){
            for(int start = 1; start <= n - length + 1; start++){
                int end = start + length - 1;
                for(int m = 2; m<=k; m++){
                    for(int mid = start; mid < end; mid += k - 1){
                        dp[start][end][m] = Math.min(
                            dp[start][end][m],
                            dp[start][mid][1] + dp[mid+1][end][m-1]
                        );
                    }
                }
                dp[start][end][1] = dp[start][end][k] + psum[end] - psum[start-1];
            }
        }
        return dp[1][n][1];
    }

    private boolean check(int length, int k){
        return length % (k - 1) == 1;
    }
}