11066번 – 파일합치기

문제

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

풀이

코드

재귀로 풀기

from sys import stdin

costs = []
minSums = []
arr = []
big = 10**8+1
  
def 최소합찾기(s, e):
  global arr, minSums
  if minSums[s][e] > 0: return minSums[s][e]
  if s == e: return 0
  minSum = big
  for i in range(s, e):
    ls, le, rs, re = s, i, i+1, e  
    minSums[ls][le], minSums[rs][re] = 최소합찾기(ls, le), 최소합찾기(rs, re)
    후보 = minSums[ls][le]+minSums[rs][re]+(costs[re])
    if ls > 0: 후보 -= costs[ls-1]
    minSum = min(minSum, 후보)
  minSums[s][e] = minSum
  return minSums[s][e]
  
t = int(input())
for _ in range(t):
  k = int(input())
  costs = []
  minSums = [[0]*(k+1) for _ in range(k+1)]
  arr = list(map(int, stdin.readline().split()))
  costs = [arr[0]]
  for i in range(1, len(arr)): costs.append(costs[i-1]+arr[i])
  print(최소합찾기(0, len(arr)-1))

하지만 이 코드는 PyPy3으로 돌려도 시간초과가 난다 ㅠ. 하지만 아래 C++은 잘 돌아간다.

#include <iostream>
#include <vector>
#include<cstring>
#include <algorithm>
using namespace std;
int chapter[501] = { 0 };
int d[501][501] = { 0 };
int go(int first,int last) {
	if (d[first][last] != -1)
		return d[first][last];
	
	if (first == last)
		return 0;
	int sum = 0;
	for (int i = first; i <= last; i++) {
		sum += chapter[i];
	}
	int ans=-1;
	for (int i = first; i <= last - 1; i++) {
		int tmp = go(first, i)+go(i+1, last)+sum;
		if (ans == -1 || ans > tmp)
		{
			ans = tmp;
		}
	}
	d[first][last] = ans;
	return ans;
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		memset(d, -1, sizeof(d));
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++)
			cin >> chapter[i];
		cout << go(1, n)<<'\n';
	}
}

왼쪽에서 오른쪽으로 채워가는 방식

from sys import stdin
import math
  
t = int(input())
for _ in range(t):
  k = int(input())
  costs = []
  minSums = [[0]*(k+1) for _ in range(k+1)]
  arr = list(map(int, stdin.readline().split()))
  costs = [arr[0]]
  for i in range(1, len(arr)): costs.append(costs[i-1]+arr[i])
  costs.append(0) # costs[-1]인 경우에는 0을 리턴해야 하기 때문
  
  for gap in range(1, k):
    for start in range(k):
      end = start + gap
      if end == k: break # 범위를 벗어나면 범춘다
      minSums[start][end] = math.inf
      for i in range(start, end):
        후보 = minSums[start][i] + minSums[i+1][end] + (costs[end]-costs[start-1])
        minSums[start][end] = min(minSums[start][end], 후보)
  print(minSums[0][k-1])