글 읽기 - 왜 시간초과가 아닐까요?

rdd6584 7년 전 0

3 * (2^999)번 만큼 순환호출이 일어나는데, 왜 시간초과가 안나는지 궁금해요...

#include<stdio.h>
int price[1000][3];
int n;

int cal(int ma, int pre)
{
	int x = 999999, y = 999999, z = 999999;

	if (ma == n)
		return 0;

	if (pre != 0)
		x = cal(ma + 1, 0) + price[ma][0];
	if (pre != 1)
		y = cal(ma + 1, 1) + price[ma][1];
	if (pre != 2)
		z = cal(ma + 1, 2) + price[ma][2];

	return x < y ? (x < z ? x : z) : (y < z ? y : z);
}

int main()
{

	scanf("%d", &n);

	for (int i = 0; i < n; i++)
		scanf("%d %d %d", &price[i][0], &price[i][1], &price[i][2]);

	printf("%d", cal(0, -1));

}

isac322 7년 전 1

데이터가 빈약하거나 시간이 너무 느슨(?)해서 그런 것 같네요...

koosaga 7년 전 1

assert(n <= 30); 해도 잘 되네요. 데이터가 많이 약한듯 합니다.

startlink 6년 전 1

수정했습니다.

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

문제

문제

출처

ICPC

왜 시간초과가 아닐까요?

rdd6584 7년 전 0

isac322 7년 전 1

koosaga 7년 전 1

startlink 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말