[BOJ] 11066 파일 합치기

https://www.acmicpc.net/problem/11066

11066번: 파일 합치기

저번 학기 알고리즘 설계 분석에서 배운 행렬 곱의 최소화 문제와 같은 알고리즘이다.

막상 수업시간에 이해를 하지 못했는데 이번에 다시 문제를 보면서 제대로 이해했다.

 

이 문제를 풀기 위해서는 위와 같은 방식으로 반복문을 돌 줄 알아야 한다.

위 처럼 반복문을 돌기 위한 코드는 다음과 같다.

for(int j=1;j<=K;j++){
        for(int i=1;i<=K-j;i++){
            int y=i, x=i+j;
            dp[y][x]=INT_MAX;
            for(int k=y;k<x;k++){
                dp[y][x]=min(dp[y][x],dp[y][k]+dp[k+1][x]+sum_[x]-sum_[y-1]);
            }
            
        }
    }

보통 반복문과는 다르게 행을 먼저 K-j만큼 반복문을 돌면 된다. 단, 참조하는 열의 값은 i+j로 두어야 한다.

 

dp[i][j]가 의미하는 것은 i번째 부터 j번째 까지 최소합이 들어있다.

따라서 점화식은 dp[y][x] = min(dp[y][k]+dp[k+1][x]+sum[x]-sum[y-1])이다.

여기서 sum[i]는 첫번째 부터 i번째까지 파일을 합치는데 드는 비용이다.

 

 

말로 풀어쓰자면 y번째 부터 x번째 까지의 최소합은 y번째 부터 k번째와 k+1번째 부터 x번째 까지의 합의 최솟값에 y번째 부터 x번째를 모두 더한 값이라고 할 수 있다.

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>

#define INF 1000000000
#define endl '\n'
#define ll long long
using namespace std;

int T,K;
int K_[501],dp[501][501],sum_[501];

void input() {
    cin>>T;
}

void init() {
    cin>>K;
    for(int i=1;i<=K;i++){
        cin>>K_[i];
        sum_[i]=sum_[i-1]+K_[i];
    }
}


int solution() {
    for(int j=1;j<=K;j++){
        for(int i=1;i<=K-j;i++){
            int y=i, x=i+j;
            dp[y][x]=INT_MAX;
            for(int k=y;k<x;k++){
                dp[y][x]=min(dp[y][x],dp[y][k]+dp[k+1][x]+sum_[x]-sum_[y-1]);
            }
            
        }
    }
    return dp[1][K];
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    while(T--){
        init();
        cout<<solution()<<endl;
    }
    return 0;
}