글 읽기 - 재귀로는 풀수가 없나요? 시간초과가 무조거나네요

kts1801 7년 전 0

시간초과 안나는 방법좀 알려주세요ㅠ

#include <stdio.h>

int n;

int DFS(int row,int state) {
	
	int ret=0;
	
	if(row==n) {
		return 1;
	}
	if(state==1) {
		ret = (ret+ DFS(row+1,2))%9901;
		ret = (ret+ DFS(row+1,3))%9901;
	}
	if(state==2) {
		ret = (ret+ DFS(row+1,1))%9901;
		ret = (ret+ DFS(row+1,3))%9901;
	}
	if(state==3) {
		ret= (ret+DFS(row+1,1))%9901;
		ret= (ret+DFS(row+1,2))%9901;
		ret= (ret+DFS(row+1,3))%9901;
	}

	
	return ret;
}

int main() {

	scanf("%d",&n);
	

	
	printf("%d",DFS(0,3)%9901);
	}
	

zlzmsrhak 7년 전 0

메모이제이션에 대해 찾아보시는 것이 좋을 것 같습니다.

컨셉은, 같은 인자에 대해 같은 값을 리턴하는 함수는 그 결과를 저장하여 중복 연산을 하지 않는 것을 말합니다.

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

문제

문제

출처

ICPC

재귀로는 풀수가 없나요? 시간초과가 무조거나네요

kts1801 7년 전 0

zlzmsrhak 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말