글 읽기 - 시간초과가 나는 이유를 전혀 모르겠습니다... 도움이 필요합니다.

yujong_lee 3년 전 0

인터넷 검색해봐도 로직에서 아무런 차이가 없는데

왜 저는 시간초과가 날까요...

도움 부탁드립니다.

#include <iostream>
#include <algorithm>
using namespace std;
int file[501]; // i번쩨 파일 크기
int sum[501];  // 1부터 i번째 파일 크기
int cache[501][501]; // i부터 j까지 비용 최소
int MAX = 10001 * 501;


int cost(int from, int to) {
	if (cache[from][to] != MAX) return cache[from][to];
	if (from == to) return cache[from][to] = 0;
	if (from + 1 == to) return cache[from][to] = file[from] + file[to];
	
	for (int mid = from; mid < to; ++mid) {
		cache[from][to] = min(cache[from][to], cost(from, mid) + cost(mid + 1, to) + sum[to] - sum[from - 1]);
	}
	return cache[from][to];
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int test_case;
	cin >> test_case;
	while (test_case--) {
		for (int i = 0; i < 501; ++i) {
			for (int j = 0; j < 501; ++j) {
				cache[i][j] = MAX;
			}
		}

		int size;
		cin >> size;

		for (int i = 1; i <= size; ++i) {
			cin >> file[i];
			sum[i] = sum[i - 1] + file[i];
		}
		cout << cost(1, size) << '\n';
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과가 나는 이유를 전혀 모르겠습니다... 도움이 필요합니다.

yujong_lee 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말