주어진 파일들을 두 개씩 합쳐서 하나의 파일로 만들 때 최소의 비용을 구하는 문제입니다. 이 문제는 DP 문제인데, x번 파일부터 y번 파일까지를 하나의 파일로 만들 때 필요한 최소 비용을 저장합니다. y - x 값이 작은 임시파일의 비용부터 구해나가면 두 임시파일을 합칠 때 각 임시파일은 y - x의 값이 구하려는 임시파일보다 작으므로 최소 비용이 저장되어있습니다. 관계식은 아래와 같게 됩니다.
cost[a][b] = min([cost[a][x] + cost[x + 1][b] for x in range(a, b)]) + sum([size[x] for x in range(a, b)])
위에서 cost[a][b]는 a번 파일부터 b 파일까지를 하나의 임시파일로 만들 때의 최소 비용, size[x]는 x번 파일의 크기입니다. 위의 식을 이용하면 결과값을 빠르게 구할 수 있습니다.
사실 이렇게 구하는 것이 맞는 것 같다고 생각하고 코드를 짜서 맞았습니다!를 띄웠는데 아직 이해는 못했습니다(???)
PS알못 OrbitHv의 PS