글 읽기 - 김치배달 시간초과 질문

mypark3424 8년 전 0

몇일동안 고민해봐도 시간초과를 줄일 수 있는 방법이 떠오르지 않습니다.

도와주시면 감사드리겠습니다!!

#include <iostream>
#include <stdio.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 1234567890
int dp[1001][1001];

int kimchi[1001];
int N, L;
int answer;

int solve(int leftKimchi, bool selectKimchi[1001], int start, int before)
{
	int & ret = dp[start][before];
	
	if (leftKimchi == 0)
	{
		return dp[start][before];
	}

	if (ret != INF)
	{
		if (ret < dp[start-1][before])
		{
			//ret = dp[start - 1][before];
			return  INF;
		}
	}

	for (int k = 0; k < N; ++k)
	{
		if (!selectKimchi[k])
		{
			dp[start][k] = min(dp[start][k], dp[start - 1][before] + ABS(kimchi[k] - kimchi[before]) * leftKimchi);
			selectKimchi[k] = true;
			cout << "dp[" << start << "]" << "[" << k << "] = " << dp[start][k] << endl;
			ret = min(ret, solve(leftKimchi - 1, selectKimchi, start + 1, k));
			selectKimchi[k] = false;
		}
	}
	return ret;
}
int main()
{
	cin >> N >> L;
	for (int i = 0; i < N; ++i)
	{
		cin >> kimchi[i];
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			dp[i][j] = INF;
		}
	}
	int leftKimchi = N;
	bool selectKimchi[1001];
	for (int i = 0; i < N; ++i)
	{
		selectKimchi[i] = false;
	}

	answer = 123456789;
	for (int i = 0; i < N; ++i)
	{
		dp[0][i] = ABS(L - kimchi[i]) * leftKimchi;
		cout << "dp[" << "0" << "][" << i << "] = " << dp[0][i] << endl;
		selectKimchi[i] = true;
		answer = min(answer , solve(leftKimchi - 1, selectKimchi, 1, i));
		cout << "answer = " << answer << endl;
		selectKimchi[i] = false;
	}
	printf("%d\n", answer);

}

yukariko 8년 전 1

좌표를 정렬된 상태로 생각한다면, dp 정의를 아래와 같이 생각해 볼 수 있습니다.

dp[left][right][pos] = 내가 [left, right] 범위의 김치를 모두 배달했고, pos 위치(left or right 중 한 곳)에 있을때, 나머지 김치를 배달할 때의 쉰 정도의 최소값

이때의 공간 복잡도는 O(N^2) 입니다.

남은것은 이제 left-1 과 right + 1 둘 중 한곳으로만 보내준다면, 재귀 함수안에 반복없이 문제를 해결할 수 있습니다.

이 때의 시간복잡도는 상태공간 O(N^2)과 거리 계산 O(N)으로 O(N^3) 이 됩니다.

여기서 거리 계산을 부분합을 통해 미리 구해준다면, 시간복잡도를 O(N^2)로 줄일 수 있습니다.

mypark3424 8년 전 0

yukariko님께서 말씀하신대로 코드를 짜봤는데 아직도 안되서 질문드립니다!!

부분합을 통해서 거리계산까지 미리하였고 이전pos와 현재 pos를 활용하여 ret값을 업데이트 해가는 식으로 코드를 짰습니다.

아직도 시간초과가 나서 뭐가 잘못됬는지 도저히 찾지를 못하고있습니다.

도와주셨으면 합니다!! 감사합니다.

#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;

	if (ret != INF && firstTime && pos == beforepos)
	{
		return ret;
	}
	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 - 1)
	{
		return ret;
	}
	else if (leftKimchi <= 1)
	{
		return ret = INF;
	}
	
	if (pos == 0)
	{
		ret += min(solve(leftKimchi - 1, left - 1, right, 0, 0), solve(leftKimchi - 1, left, right + 1, 1 ,0));
	}
	else
	{
		ret += min(solve(leftKimchi - 1, left - 1, right, 0, 1), solve(leftKimchi - 1, left, right + 1, 1,1));
	}
	

	return ret;

}
int main()
{
	cin >> N >> L;
	for (int i = 0; i < N; ++i)
	{
		cin >> kimchi[i];
	}
	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;
	answer = 123456789;
	int before;
	//부분합 구하기

	partialsum[0] = 0;
	for (int i = 1; i < N; ++i)
	{
		partialsum[i] = kimchi[i] - kimchi[i-1];
		partialsum[i] += partialsum[i - 1];
	}
	for (int i = 0; i < N; ++i)
	{
		firstTime = false;
		dp[i][i][0] = ABS(L - kimchi[i]) * leftKimchi;
		//cout << "dp[" << "0" << "][" << i << "] = " << dp[0][i] << endl;
		before = solve(leftKimchi, i, i, 0,0);
		//cout << "before = " << before << endl;
		answer = min(before, answer);
		/*for (int p = 0; p < N; p++)
		{
			for (int j = 0; j < N; j++)
			{
				for (int k = 0; k < 2; k++)
				{
					dp[p][j][k] = INF;
				}

			}
		}*/

	}
	printf("%d\n", answer);

}

bluespace 8년 전 0

cheer up

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

문제

문제

출처

ICPC

김치배달 시간초과 질문

mypark3424 8년 전 0

yukariko 8년 전 1

mypark3424 8년 전 0

bluespace 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말