[Algorithm] 11066: 파일 합치기

📦11066: 파일 합치기

---

[알고리즘 풀이] 강동규
Reviewed by Kade Kang (devkade12@gmail.com)
Reviewed:: 2024-02-19
문제 확인하기

풀이

• Matrix_calcuation-11049 문제와 거의 동일한 문제이다.
• 이 문제에서 주의할 점은 임시파일을 만들면서 중복적으로 발생하는 비용이다.
• C1, C2, C3, C4 = 40, 30, 30, 50 을 예로 들어보자.
• 문제대로 합쳐 보면
  • C2 + C3 = 60 = X1
  • X1 + C1 = 100 = X2
  • X2 + C4 = 150 = X3
  • 최종 = X1(C2 + C3) + X2(C1 + C2 + C3) + X4(C1 + C2 + C3 + C4)
• 때문에 해당 부분에 집중해서 변형해준다.
• 3중 for문은 Matrix_calcuation-11049 의 풀이를 참고하면 된다.

• 풀이

  • 이 문제는 1시간을 고민해도 전혀 갈피를 잡지 못하겠어서 결국 https://cocoon1787.tistory.com/318의 풀이를 참고했다. 확실히 DP 문제에 약하다고 느껴진다.

  • dp[n][m] 는 n 에서 m 까지의 범위를 행렬 연산했음을 의미한다.

  • 3중 for 문을 사용하여 행렬 연산의 범위, 시작 지점, 범위 연산을 지정해 계산한다.

  • i 는 행렬의 범위를 지정한다. i = 2 일 경우, dp[n][m] 에서 m-n, n과 m 사이의 거리, 차이가 2라는 뜻이다.

  • j 는 행렬의 시작 지점을 말한다. j = 3, i = 2 인 경우 dp[3][5] 로 3에서 시작해서 5번째까지의 행렬을 구한다.

  • mid 는 범위 안에서의 실질적인 연산을 진행한다. dp[3][10] 을 구한다고 하면 mid 는 3~10 의 값이고, 반복문을 돌면서 dp[3][3], dp[3][4], … 를 구한다.

  • 최종적으로는 dp[1][N] 을 구하면 1~N 까지의 행렬 연산의 최솟값을 구할 수 있다.

  • 혼자 생각할 때 dp로 느낌이 들기는 했지만 어떻게 풀어야 할지 감이 오지 않았다. 해당 문제를 풀이하는 방식이 이해를 하니까 끄덕일 수 있었지만 체득이 필요할 것 같다.

  Link to original

#include <iostream>
 
#define endl '\n'
using namespace std;
 
int T, N;
int Info[501][2];
int dp[501][501];
 
void Input(){
    cin >> N;
    for(int i=1; i<=N; i++) {
        cin >> Info[i][0];
        Info[i][1] = Info[i-1][1] + Info[i][0];
    }
}
 
void Solution(){
    while(T--){
        Input();
        for(int i=1; i<N; i++){
            for(int j=1; i+j<=N; j++){
                dp[j][i+j] = INT32_MAX;
                for(int k=j; k<=i+j; k++){
                    dp[j][i+j] = min(dp[j][i+j], dp[j][k] + dp[k+1][i+j]                                       + Info[i+j][1] - Info[j-1][1]);
                }
            }
        }
        cout << dp[1][N] << endl;
    }
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> T;
    Solution();
 
    return 0;
}