다이나믹 프로그래밍
- 작은 문제의 답이 큰 문제의 답을 계산할 때 활용
- 두 가지 풀이 방법이 있음
- 상향식 풀이: for 문 돌면서 작은 문제부터 답을 계산
- 하향식 풀이: 분할정복 형태로 문제를 쪼개면서 재귀로 구현
- 점화식을 세울 때
- 작은 문제의 답부터 생각해볼것
- 큰 문제의 답을 작은 문제 답으로 계산할 수 있는지 생각해볼것
- 메모이제이션
- 초기값 설정을 잘 해야 함 (메모리를 한칸 더 크게 잡는다던가)
노트
1) 지금 단계의 해답 = 부분문제의 해답 + 추가 계산
2) 파이썬이 느리기 때문에 상향식으로 풀어야 함
3) 상향식으로 풀때는
- 작은 문제부터 답을 만들고
- 큰 문제는 작은문제 답을 조합해서 만든다
- 이 문제에서는 '길이'가 1일 때 답을 먼저 구하고 (dp 메모리의 대각선)
- 길이를 증가시켜가며 답을 구한다
4) 누적합을 계산해두면 누적합의 차를 이용해 부분합을 구할 수 있다.
"""
psum[i] = 앞에서부터 숫자 i 개 숫자 누적합
psum[b] - psum[a] = (앞에서부터 숫자 b 개 합) - (앞에서부터 숫자 a 개 합)
"""
풀이
1) 점화식
"""
DP
sidx부터 eidx(포함)까지 부분합은 아래와 같이 계산
dp[sidx][eidx] = dp[sidx][i] + dp[i+1][eidx] + psum[eidx+1] - psum[sidx]
"""
import sys
# sys.setrecursionlimit(10**6)
sys.stdin = open('./11066.txt')
T = int(input())
for t in range(T):
n = int(input())
data = list(map(int, input().split()))
psum = [0 for _ in range(n+1)]
for i in range(1, n+1):
psum[i] = psum[i-1] + data[i-1]
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
# 가장 작은 부분문제부터 푼다
# 길이가 1인 부분문제가 가장 작은 부분문제다
# 길이를 증가시켜가며 부분문제의 답을 계산한다
for gap in range(1, n):
for s in range(n):
sidx = s
eidx = s + gap
if eidx == n:
break
dp[sidx][eidx] = sys.maxsize
for i in range(sidx, eidx):
sub_ans = dp[sidx][i] + dp[i+1][eidx]
dp[sidx][eidx] = min(dp[sidx][eidx], sub_ans)
dp[sidx][eidx] += psum[eidx+1] - psum[sidx]
print(dp[0][n-1])
