[백준] 11066번 파일 합치기 ★★★

💡문제접근

• 머리로 문제를 이해하는 것은 성공했지만 코드를 짜는 부분에 대해서 정말 어렵다고 느껴서 어떤 식으로 접근해야할지에 대해서 확인해보기 위해서 구글링을 시도했다. 코드를 보지 않았고 어떤 방식으로 접근을 하는지에 대해 설명하자면 다음과 같다.

💡테스트케이스

입력

1
4
40 30 30 50

출력

300

---

표로 나타내기에 앞서 편의상 축약된 표현을 사용할 예정이니 이 부분을 이해하길 바랍니다.
ex. AB : 파일 A와 파일 B를 합친 비용

	A	B	C	D
A	0	AB	AB + CC + ABC or AA + BC + ABC	AB + CD + ABCD
B	0	0	BC	BB + CD + BCD or BC + DD + BCD
C	0	0	0	CD
D	0	0	0	0

	40	30	30	50
40	0	70	160	300
30	0	0	60	170
30	0	0	0	80
50	0	0	0	0

📌 Python3 제출 결과는 시간초과(TLE), PyPy3로는 AC
📌 DP문제는 풀어도 풀어도 어려운 문제를 풀이를 보면 확실히 난이도가 체감이 상당히 높은 것 같다.

💡코드(메모리 : 126136KB, 시간 : 1988ms, PyPy3로 제출)

import math
import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    K = int(input())
    dp = [[0] * K for _ in range(K)]
    chapter = list(map(int, input().strip().split()))

    for i in range(1, K):
        for j in range(i-1, -1, -1):
            temp = math.inf
            for k in range(i-j):
                temp = min(temp, dp[j][j+k] + dp[j+k+1][i])
            dp[j][i] = temp + sum(chapter[j:i+1])

    print(dp[0][K-1])

💡소요시간 : 2h