백준 11066번 파일 합치기

문제 링크 : https://www.acmicpc.net/problem/11066

11066번: 파일 합치기

 

문제 요약

여러 파일들이 주어졌을 때 파일들을 두 개씩 합쳐서 여러 장들이 연속이 되도록 파일을 합쳐나가

최종적으로 하나의 파일로 되도록한다.

두 개의 파일으 합칠 때 필요한 비용은 두 파일 크기의 합이며 출력값으로 최종 파일을 완성하는데 필요한 비용의 총 합을 출력한다.

풀이

다이나믹 프로그래밍 문제입니다!

이 문제가 dp로 풀 수 있는 이유는 바로 위에 빨간 색으로 강조한 "여러 장들이 연속이 되도록" 이라는 조건 때문이다.

예를 들어 연속적인 파일 C1, C2, C3, C4 가 있다면 이 파일들을 두 그룹으로 나눌 수 있게된다.

• (C1)(C2,C3,C4)
• (C1,C2)(C3,C4)
• (C1,C2,C3)(C4)

그럼 이 그룹들은 각각의 부분 문제들이 되기 때문에 dp를 이용 가능하다.

이 문제에서 d[i][j]는 파일 i ~ 파일 j 를 합치는데 드는 비용의 최소값이고,

두 그룹을 나누기 위한 중간 값 k를 만들어줘야한다.

위의 예시에서 k는 순서대로 1,2,3 이 된다. (k의 범위는 0 ~ j-1)

따라서

• d[i][j] = d[i][k] * d[k+1][j] + (i~j를 합치는데 드는 비용) 

이렇게 만들어준 부분 문제들을 다시 재귀호출한다.

 

소스 코드

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
int d[501][501]; // d[i][j] : i~j 합의 최소비용
int a[501];
 
int go(int i, int j) {
    //기저 사례
    if (i == j) return 0;
    if (d[i][j] != -1) return d[i][j]; //이미 계산했다면
    int sum = 0;
    int &ans = d[i][j];
    for (int k = i; k <= j; k++) { //합치는데 드는 비용
        sum += a[k];
    }
    for (int k = i; k <= j - 1; k++) { //순서대로 분할
        int temp = go(i, k) + go(k + 1, j) + sum;
        if (ans == -1 || ans > temp) {
            ans = temp;
        }
    }
    return ans;
}
int main()
{
    int t; scanf("%d", &t);
    while (t--) {
        memset(d, -1, sizeof(d));
        int k; scanf("%d", &k);
        for (int i = 1; i <= k; i++) {
            scanf("%d", &a[i]);
        }
        printf("%d\n", go(1, k));
    }
    return 0;
}

 

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~