BOJ(파일합치기) 11066

작성일 | In

11066 파일 합치기

  • 중요한 포인트는 2가지다.
  • 연속한 파일만 합칠 수 있으며

  • 파일은 2개의 연속된 파일을 합친 것이다.

  • A1,A2,A3,A4,A5란 파일이 있다고 하자.
  • 이 파일을 합치는 방법은 4가지가 있다.
  • (A1),(A2,A3,A4,A5) : (1-1)/(2-5) = > (1-5)
  • (A1,A2),(A3,A4,A5) : (1-2)/(3-5) => (1-5)
  • (A1,A2,A3),(A4,A5) : (1-3)/(4-5) => (1-5)

  • (A1,A2,A3,A4)(A5) : (1-4)/(5-5) => (1-5)

  • 이 네가지 방법 말고는 다섯가지 파일을 합치는 방법이 없다.
  • 점화식을 구현할 때, 개수를 중요하게 여기지만. 개수보다 더 중요한게. file이 개수는 같지만, 구성되어 있는 파일이 다르므로 다른 경우로 잡아야 한다

  • 따라서 파일의 시작 위치와 끝 위치를 알게 되면, 나타낼 수 있다.

  • 1번부터 5번까지의 파일을 합친 것.
  • D[i][j] = i번째부터 j번째 파일을 합치는 최소 비용으로 정의
  • 예를 들어 첫번째는 D[1][1] + D[2][5] + 1~5 파일크기 (이게 파일을 합치는 비용이 된다)

일반화

  • i번째부터 j번째 까지 파일이 있다.
  • D[i][j]
  • D[i][j]를 합치는 방법은 다음과 같이 나타낼 수 있다
  • (Ai, Ai+1, … Ak)(Ak+1… Aj-1,Aj)
  • Min(D[i][k] + D[k+1][j] + i번째부터 j번째까지 파일 크기의 합)을 더해주면 된다.
  • 변수의 범위는 i<= k <= j-1
  • 어떻게 for문을 돌아야 할지가 애매하다.
  • 이 문제도 팰린드롬 문제와 크기가 문제의 크기를 나타낸다.
  • 다이나믹 에서의 작은 문제를 정의하는 크기가 i~j까지 포함된 파일의 크기가 된다.
def go(i, j):
    if i == j:
        return 0
    if d[i][j] != -1:
        return d[i][j]
    ans = d[i][j]
    cost = sum(a[i:j+1])
    for k in range(i, j):
        temp = go(i,k) + go(k+1,j) + cost
        if ans == -1 or ans > temp:
            ans = temp
    d[i][j] = ans
    return ans

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int,input().split()))
    d = [[-1]*n for _ in range(n)]
    print(go(0,n-1))
  • 문제의 시간제한 때문에 시간초과를 받을 수 밖에 없다.
#include <cstdio>
#include <cstring>
int a[501];
int d[501][501];
int go(int i, int j) {
    if (i == j) {
        return 0;
    }
    if (d[i][j] != -1) {
        return d[i][j];
    }
    int &ans = d[i][j];
    int sum = 0;
    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 n;
        scanf("%d",&n);
        for (int i=1; i<=n; i++) {
            scanf("%d",&a[i]);
        }
        printf("%d\n",go(1, n));
    }
    return 0;
}


import sys


def sol(N, data):
    S = [0] * (500 + 1)
    D = [[0 for j in range(500 + 1)] for i in range(500 + 1)]
    K = [[0 for j in range(500 + 1)] for i in range(500 + 1)]
    for i in range(1, N + 1):
        S[i] = S[i - 1] + data[i - 1]
    for i in range(1, N + 1):
        D[i - 1][i] = 0
        K[i - 1][i] = i
    for d in range(2, N + 1):
        for i in range(0, N - d + 1):
            j = i + d
            D[i][j] = 10 ** 9
            for k in range(K[i][j - 1], K[i + 1][j] + 1):
                v = D[i][k] + D[k][j] + S[j] - S[i]
                if D[i][j] > v:
                    D[i][j] = v
                    K[i][j] = k
    return D[0][N]


if __name__ == "__main__":
    input = sys.stdin.readline
    T = int(input())
    for i in range(T):
        N = int(input())
        data = list(map(int, input().split()))
        sys.stdout.write(str(sol(N, data)) + "\n")

참고자료 codeplus

0%