글 읽기 - N=30만 넣어도 30초정도 걸리던데 왜그런가요?

cblimmm 7년 전 0

일단 답도 틀렸다고 나오지만 그 이전에 DEV C++로 돌려봤을때 N=30정도만 넣어도 답이 나오는데까지 30초가량이 걸리더라고요

40은 입력해봤는데 3분째 지금 답이 안나옵니다...

시간복잡도는 O(n)으로 짠 것 같은데 어디가 문제인가요?

#include <stdio.h>
int main(){
	int N;
	scanf("%d", &N);
	long int sum=0;
	long int a[N+1][10];
	a[1][0]=0;
	int i,j;
	for(i=1; i<=9; i++){
		a[1][i]=1;
	}
	for(i=2; i<=N; i++){
		a[i][0]=a[i-1][1];
		a[i][9]=a[i-1][8];
		for(int j=1; j<=8; j++){
			a[i][j]=(a[i-1][j+1]+a[i-1][j-1])%1000000000;
		}
	}
	for(i=0; i<=9; i++){
		sum+=a[N][i];
	}
	sum=sum%1000000000;
	printf("%ld", sum);
	return 0;
}

cblimmm 7년 전 0

조금 소스 고쳐서 채점기에 넣으니 정답이 뜨는걸로 봐선 DEV나 제 컴의 문제같은데 왜이럴까요...

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

문제

문제

출처

ICPC

N=30만 넣어도 30초정도 걸리던데 왜그런가요?

cblimmm 7년 전 0

cblimmm 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말