🥚문제링크

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

• 다이나믹 프로그래밍

---

🍳코드

topdown으로 풀었을 때 시간초과가 났다 😅

import sys
input = sys.stdin.readline


for _ in range(int(input().strip())):
    k = int(input().strip())
    arr = [0] + list(map(int, input().split()))

    # sums[i] = 1~i까지의 파일 크기 합
    sums = [0]*(k+1)
    for i in range(1, k+1):
        sums[i] = sums[i-1] + arr[i]

    # dp[i][j] = 파일 i ~ j까지 합칠 때 필요한 최소비용
    dp = [[-1]*(k+1) for _ in range(k+1)]

    # 초기화
    for i in range(1, k+1):
        dp[i][i] = 0

    # 대각선방향↘ 으로 순회할 수 있게 함
    # (1, 2) -> (2, 3) -> (3, 4) -> (1, 3) -> (2, 4) -> ...
    for i in range(1, k+1):
        for start in range(1, k+1):
            end = start + i
            if end > k:
                continue

            min_cost = 10**9
            for mid in range(start, end):
                min_cost = min(min_cost, dp[start][mid] + dp[mid+1][end])
            dp[start][end] = min_cost + sums[end] - sums[start-1]

    print(dp[1][k])

---

🧂아이디어

DP (Bottom up)

• dp[i][j] = 파일 i ~ j까지를 합치는 데 드는 최소 비용

• start파일부터 end파일까지를 합칠 때 최소 비용을 구하는 식은 아래와 같다.

• dp[start][end] = min(start <= mid < end)(dp[start][mid] + dp[mid+1][end]) + (i부터 j까지의 파일 크기 합)

• 말로 풀어서 설명하자면, start ~ end를 합치는 최소 비용은 start <= mid < end라고 했을 때, (1)start ~ mid를 합치는 비용과 mid+1 ~ end를 합치는 비용의 합이 최소인 것 + (2)start~end의 파일 크기

• dp[i][i] = 0으로 초기화한다.

• 대각선방향↘ 으로 2차원 리스트 dp를 순회할 수 있게 이중 for문을 짜고,
  그 내부에 start <= mid < end일 때 dp[start][mid] + dp[mid+1][end]의 최소값을 구할 수 있도록 다시 for문을 써준다. 즉, 3중 for문이 필요하다.

• dp[1][k]의 값이 우리가 원하는 답이 된다.

참고: https://js1jj2sk3.tistory.com/3