글 읽기 - 시간초과 질문드립니다.

mypark3424 8년 전 0

아래와 같이 다시 최대한 만들어봤는데요 중복 처리를 못해서 그런지 계속해서 시간초과가 납니다.

어떻게 해야 해결 가능한지 좀 알려주셨으면 합니다.

감사합니다.

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

#define ABS(a)(((a) < (0))?-(a):(a))
#define min(a,b) ((a) > (b) ? (b) : (a))
#define max(a,b) ((a)>(b)? (a):(b))
#define INF 123456789

int dp[1001][1001][3];

int partialsum[1001];
int kimchi[1001];
int N, L;
int answer;
bool firstTime;
int solve(int leftKimchi, int left, int right, int pos, int beforepos)
{
	int & ret = dp[left][right][pos];

	if (left < 0 || right < 0 || left > N || right > N) return INF;

	ret = 0;
	//firstTime = true;
	if (left != right)
	{
		if (beforepos == 0)
		{
			if (pos == 0)
			{
				ret = (partialsum[left + 1] - partialsum[left]) * leftKimchi;
				//ABS(kimchi[left + 1] - kimchi[left]) * leftKimchi;
			}
			else
			{
				ret = (partialsum[right] - partialsum[left]) * leftKimchi;
				//ABS(kimchi[left] - kimchi[right]) * leftKimchi;

			}
		}
		else if (beforepos == 1)
		{
			if (pos == 0)
			{
				ret = (partialsum[right] - partialsum[left]) * leftKimchi;
				//ABS(kimchi[left] - kimchi[right]) * leftKimchi;
			}
			else
			{
				ret = (partialsum[right] - partialsum[right-1]) * leftKimchi;
				//ABS(kimchi[right-1] - kimchi[right]) * leftKimchi;

			}
		}
	
		//cout << ret << endl;
	}
	//cout << "ret = " << ret << " " << "left = " << left << " right = " << right << " pos = " << pos << " leftKimchi = " << leftKimchi << endl;

	if (leftKimchi == 1 && left == 0 && right == N)
	{
		//cout << "reach OK ret = " << ret << endl;
		return ret = dp[left][right][pos];
	}
	else if (leftKimchi <= 1)
	{
		return ret = INF;
	}

	
	if (pos == 0)
	{
		ret = ret + min(solve(leftKimchi - 1, left - 1, right, 0, 0), solve(leftKimchi - 1, left, right + 1, 1 ,0));
	}
	else
	{
		ret = ret + min(solve(leftKimchi - 1, left - 1, right, 0, 1), solve(leftKimchi - 1, left, right + 1, 1,1));
	}
	//cout << "return = " << ret << endl;
	return ret;

}
int main()
{
	int LIndex = -1;
	cin >> N >> L;
	bool firstEnter = true;
	for (int i = 0; i <= N; ++i)
	{
		cin >> kimchi[i];
		if (kimchi[i] > L && firstEnter)
		{
			firstEnter = false;
			int temp = kimchi[i];
			LIndex = i;
			kimchi[i] = L;
			kimchi[i + 1] = temp;
			i = i + 1;
		}
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			for (int k = 0; k < 2; k++)
			{
				dp[i][j][k] = INF;
			}
			
		}
	}
	int leftKimchi = N;
	int before;
	//부분합 구하기

	partialsum[0] = 0;
	for (int i = 1; i <= N; ++i)
	{
		partialsum[i] = kimchi[i] - kimchi[i-1];
		partialsum[i] += partialsum[i - 1];
	}

	answer = solve(leftKimchi+1, LIndex, LIndex, 0, 0);
	printf("%d\n", answer);

}

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

문제

문제

출처

ICPC

시간초과 질문드립니다.

mypark3424 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말