[BOJ_11066_RN] 파일 합치기 Problem Solving

문제 출처 : https://www.acmicpc.net/problem/11066

문제 해결에 필요한 알고리즘 : DP ( Dynamic Programming )

해설

합쳐야 하는 파일을 두 수열로 나눌 수 있다. 최적으로 합쳐야 하는 구간을 i ~ j 라고 할 때 임의의 k에 대해 ( i <= k < j ) i ~ k 구간과 k + 1 ~ j 구간으로 나눌 수 있다. 이렇게 작은 부분문제로 나누어 문제를 해결 할 수 있다.

dp[i][j] = i ~ j 까지 최적으로 합친 값

ar[n] = n번째 파일의 크기

라고 할 때

라는 식이 성립한다.

이 때  이 식은 부분합을 이용해  만에 구할 수 있다.

시간 복잡도

테스트케이스의 수인 T의 제한은 문제에 나와있지 않으며 대략 1개의 케이스를 통과할 시간복잡도가 된다면 대회에서 문제를 해결 할 수 있었다.

이 코드는 find함수가  만큼 호출된다. 또 함수 내부의 반복문이  만큼 반복된다. 그래서 이 코드의 시간복잡도는  라는 시간복잡도를 갖게 된다.

시간복잡도는 느리다고 생각할 수 있지만, 모든 DP 테이블을 채우지 않고 함수 내부의 반복문도 길이가 짧아지기 때문에 실제론 더 나은 시간복잡도를 갖는다.

파일 합치기 코드 [ C ]

#include <string.h>
#include <stdio.h>
int ar[501], dp[501][501], mem[501];
int min(int i, int j) {
    return i < j ? i : j;
}
int find(int i, int j) {
    if (i == j) return 0;
    if (dp[i][j] != -1) return dp[i][j];
    int k;
    dp[i][j] = 987654321;
    for (k = i; k < j; ++k) {
        dp[i][j] = min(dp[i][j], find(i, k) + find(k + 1, j));
    }
    return dp[i][j] += mem[j] - (i > 0 ? mem[i - 1] : 0);
}
int main() {
    int t;
    scanf("%d", &t);
    for (; t--; ) {
        int i, j, n;
        memset(dp, -1, sizeof dp);
        scanf("%d", &n);
        for (i = 0; i < n; ++i) {
            scanf("%d", ar + i);
            mem[i] = ar[i] + (i > 0 ? mem[i - 1] : 0);
        }
        printf("%d\n", find(0, n - 1));
    }
    return 0;
}