글 읽기 - 시간 초과 해결 해주세요ㅠㅠㅠ

alohajihwan 8년 전 0

시간 복잡도 계산을 잘 못해서 시간 초과나는 원인이랑 제 코드 시간 복잡도 구하는 방법좀 알려주세요ㅠㅠㅠㅠ

#include<stdio.h>
#include<iostream>
#include<memory.h>
using namespace std;

#define INF 9897421
int n,jump;
int train[50011];

int dp[50011][9];
int solve(int now , int k)
{
	if(now > n && k != 4) return -INF;
	if(k == 4) return 0;
	int & ret = dp[now][k];
	if(ret != -1) return ret;

	int sum= 0;
	ret = 0;
	ret = max(ret , solve(now+1,k));
	for(int i=0;i<jump;i++){
		if(now+i <= n){
			sum+=train[now+i];
			ret = max(ret, solve(now+i+1,k+1) + sum);
		}
	}
	return ret;
}
int main()
{
	cin >> n;
	for(int i=1;i<=n;i++)
		scanf("%d",&train[i]);
	cin >> jump;
	memset(dp,-1,sizeof(dp));
	
	cout << solve(1,1) << endl;
}

na982 8년 전 3

대략 적으로 N^2에 N은 5만입니다;

원인은 재귀함수 안에 있는 반복문을 제거 해야 합니다.

ret = max(solve(now + 1, k), solve(now + jump, k+1) + sum[train[now] - train[now+k-1]])

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

문제

문제

출처

ICPC

시간 초과 해결 해주세요ㅠㅠㅠ

alohajihwan 8년 전 0

na982 8년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말