글 읽기 - 왜 시간 초과 뜨는지 모르겠습니다.

tjrdnd0511 4년 전 0

10이나 20등 0으로 끝나는 수에 대한 입력을 고려하지 않아서 답도 정확히 나오는 건 아니지만

제가 생각하기엔 시간 복잡도가 44*44 정도 밖에 안되는 거 같은데 돌려보면 시간초과 뜹니다.

왜그런지 좀 알려주세요...

#include <stdio.h>
#include <string.h>


char num[44];
int div[44];
int len;
int mat[44][44];
int dNum = 1;

int main(void)
{
	int len = 0;
	int sum = 0;
	char c ;

	for (int i = 0; (c=getchar()) != '\n'; i++)
		num[i] = c;
		
	len = strlen(num);

	for (int r = 0; r < len; r++)
		for (int c = 0; c <= r/2; c++)
			if (r > 1 && c > 0)
				mat[r][c] = mat[r - 1][c] + mat[r - 2][c - 1];
			else
				mat[r][c] = 1;
	div[0] = -1;
	dNum = 1;
	for (int i = 0; i < len; i++)
		if (num[i] - '0' > 3)
			div[dNum++] = i;
	div[dNum] = len-1;
	int mul = 1;
	for (int i = 1; i <= dNum; i++)
	{
		sum = 0;
		for (int j = 0; j <= (div[i] - div[i - 1]) / 2; j++)
			sum += mat[div[i] - div[i - 1]][j];
		mul *= sum;
	}
	printf("%d\n", mul);
	return 0;
}

yomyom0824 4년 전 0

시간 복잡도를 잘못 생각하신 듯 합니다.

그냥 구한다면, 시간복잡도는 n^2이 아니라 그것보다 훨씬 클 것 같습니다.

문제에서 칸막이를 놓는 적절한 위치를 찾는다면, 이 문제는 또다시 나머지 뒤 숫자들을 쪼개는 갯수를 구하는

subproblem으로 회귀하게 됩니다.

이를 메모이제이션으로 나중에 또 계산해주지 않기 위해서 저장해 놓아야 합니다.

즉, 다이나믹 프로그래밍으로 구해야 할 것으로 생각됩니다.

tjrdnd0511 4년 전 1

답변 감사합니다. 음.. 그냥 구한건 아니고 dp로 한다고 하긴 했는데 안돼서 보니까 getchar()로 입력받는 경우에 개행 문자가 입력되어야 종료 되게 하면 입력이 종료가 안돼서 문제가 된 것 같습니다. scanf로 해서 다시 해보니까 시간 초과는 안 떠서 다시 풀어봐야 할 거 같습니다. 다시 한번 답변 감사합니다.

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

문제

문제

출처

ICPC

왜 시간 초과 뜨는지 모르겠습니다.

tjrdnd0511 4년 전 0

yomyom0824 4년 전 0

tjrdnd0511 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말