글 읽기 - 14722번 우유도시 시간초과....

rygsa123 6년 전 0

재귀함수 때문인가싶은데 시간초과가 나네요..

논리적으로는 정확한거 같은데...

시간초과를 면할만한 좋은 방법 뭐 없을까요?? ㅜㅜ

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

enum { STRAWBERRY, CHOCO, BANANA };

int m[1002][1002];
int dri[1002][1002];
int N;
int now=BANANA;
//(N-1) * 2

int f(int prev, int x, int y)
{
	if(dri[x][y]<prev)
	{
		dri[x][y]=prev;
		if(now==STRAWBERRY  && m[x][y] == CHOCO)     { dri[x][y]++; now=CHOCO;}
		else if(now==CHOCO  && m[x][y] == BANANA)    { dri[x][y]++; now=BANANA;}
		else if(now==BANANA && m[x][y] == STRAWBERRY){ dri[x][y]++; now=STRAWBERRY;}
	}
	
	if(x<N)f(dri[x][y],x+1,y);
	if(y<N)f(dri[x][y],x,y+1);
}


int main()
{	
	scanf("%d",&N);
	
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
			scanf("%d",&m[i][j]);
			
	f(0,1,1);
	printf("%d ",dri[N][N]);
}

djm03178 6년 전 0

단순히 DFS가 아닌 메모이제이션을 통해 해결해 보세요.

그리고 f는 값을 반환해야 합니다. 아무것도 반환할 필요가 없다면 void를 써야 합니다.

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

문제

문제

출처

ICPC

14722번 우유도시 시간초과....

rygsa123 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말