글 읽기 - C++ 재귀 시간초과

ekdlemdjq456 3년 전 0

다른 해설을 보면 재귀를 해도 시간초과가 안 나는 것 같던데 왜 시간초과가 날까요....??

일단 답은 잘 찾는 것 같습니다.

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAX_BOOK 501
int T, n;
int books[MAX_BOOK] = { 0, };
int sum[MAX_BOOK] = {0, };

void input() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> books[i];
        sum[i] = sum[i-1] + books[i];
	}
	
	
}

int dp_find(int start, int finish) {
	if (start == finish) {
		return 0;
	}
	if (start+1 == finish)
		return (books[start]+books[finish]);
	
	int ret = 10000000;
	for (int i = start; i < finish; i++) {
		ret = min(ret, dp_find(start, i) + dp_find(i + 1, finish));
	}
	return (ret+sum[finish]-sum[start-1]);
}

int main(int argc, char* argv[]) {
	cin >> T;
	for (int i = 0; i < T; i++) {
		input();
		cout << dp_find(1, n) << "\n";
		memset(books, 0, sizeof(int)*(n+1)*(n+1));
	}

	return 0;
}

djm03178 3년 전 1

함수 이름을 dp_find라고 지으셨지만 실제로는 dp를 하고 있지 않습니다. 메모이제이션을 이용한 dp가 이루어져야 중복된 계산을 하지 않게 됩니다.

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

문제

문제

출처

ICPC

C++ 재귀 시간초과

ekdlemdjq456 3년 전 0

djm03178 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말