글 읽기 - 시간초과 에러에 따른 질문입니다.

yeongjae8066 4년 전 0

vs에서 테스트하는데

그 전엔 잘 나오는 것 같습니다

약 N값이 5000을 넘는 순간

프로그램이 동작을 중지하는데 코드에 문제가 있다고 보면 되는건가요?

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

long arr[10] = { 0 };
void page(int n);
void search(int k, int n, int div);

int main()
{
	int i, N;
	scanf("%d", &N);

	page(N);

	for (i = 0; i < 10; i++)
	{
		printf("%ld ", arr[i]);
	}
	return 0;
}

void page(int n)
{
	int value;

	if (n == 1)
	{
		arr[1]++;
	}
	else
	{
		search(n, n, 10);
		page(n - 1);
	}
}

void search(int k, int n, int div)
{
	int value;
	if (k/div != 0) 
	{
		value = n % div;
		arr[value]++;
		n = n / div ;
		if (n != 0) {
			search(k, n, 10);
		}
	}
	else
	{
		arr[n]++;
	}
}

djm03178 4년 전 1

프로그램이 작동을 중지하는 건 재귀호출이 너무 깊어져 스택이 터졌기 때문입니다.

그를 해결하더라도 이 문제는 완전탐색으로는 풀 수 없습니다. N까지의 모든 수의 모든 자릿수를 검사하는 데에는 O(N*logN) 시간이 걸립니다.

수학적으로 접근해서 더 빠르게 계산하는 방법을 생각해야 합니다.

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

문제

문제

출처

ICPC

시간초과 에러에 따른 질문입니다.

yeongjae8066 4년 전 0

djm03178 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말