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

ksq111 6년 전 0

dp를 이용해서 푸는데 혹시나 시간초과가 왜 나는지 알 수 있을까요?

#include<stdio.h>

#define COM 20
#define FUND 300

int arr[COM][FUND];
int dp[COM][FUND] = { 0, };
int path[COM][FUND] = { 0, };
int path_process[COM];

int m, n;

int dynamic(void)
{
	int i, j, k,t;
	int max;

	for (i = 1; i <= n; i++)//회사 루프
	{
		for (j = 1; j <= m; j++)//돈 루프
		{
			for (k = 0; k <= j; k++)//각 회사마다 돈 루프
			{
				t = dp[i - 1][j - k] + arr[i][k];
				if (t > dp[i][j]){
					dp[i][j] = t;
					path[i][j] = k;//i번쨰 기업이 투자한 금액
					//printf("검증값[%d %d]:%d\n",i,j,dp[i][j]);
				}
			}
			//max = dp[i][j];
		}
	}


	return dp[n][m];
}

void Position(int n, int m)
{
	if (n == 0)
		return;
	Position(n - 1, m - path[n][m]);
	printf("%d ", path[n][m]);
}
int main()
{
	int z;
	int i, j, k;
	

	scanf("%d %d", &m, &n);


	for (i = 1; i <= m; i++)
	{
		scanf("%d", &z);

		for (j = 1; j <= n; j++)
		{
			scanf("%d", &arr[j][z]);
		}
	}

	

	//각 기업에 투자한 액수

	
	printf("%d\n", dynamic());
	Position(n, m);//기업의 수, 자금
	
	return 0;

}

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

문제

문제

출처

ICPC

시간 초과 질문드립니다

ksq111 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말