글 읽기 - 시간초과

xotmd17 6년 전 0

값이 저장된 곳은 그곳에서 출발하는것 이기 때문에 그곳의 값만 가져오는 것으로 중복을 제거 했습니다.

시간초과가 뜨는데 풀이나 알고리즘이 잘못 된것인가요?

#include<iostream>
using namespace std;
int Map[500][500];
int D[500][500];
int N, M;

int Loop(int i, int j)
{
	if(i==0 && j==0)
		return D[0][0];

	if(Map[i][j] < Map[i-1][j] && i-1 >=0) // 위쪽
		if(D[i-1][j] != 0)
			D[i][j] += D[i-1][j];
		else
			D[i][j] += Loop(i-1, j);
	if(Map[i][j] < Map[i][j-1] && j-1 >=0) // 왼쪽
		if(D[i][j-1] != 0)
			D[i][j] += D[i][j-1];
		else
			D[i][j] += Loop(i, j-1);
	if(Map[i][j] < Map[i+1][j] && i+1 < N) // 아래쪽
		if(D[i+1][j] != 0)
			D[i][j] += D[i+1][j];
		else
			D[i][j] += Loop(i+1, j);
	if(Map[i][j] < Map[i][j+1] && j+1 < M) // 오른쪽
		if(D[i][j+1] != 0)
			D[i][j] += D[i][j+1];
		else
			D[i][j] += Loop(i, j+1);

	return D[i][j];
}

int main()
{
	cin >> N >> M;
	D[0][0] = 1;
	for(int i=0; i<N; i++)
		for(int j=0; j<M; j++)
			cin >> Map[i][j];

	cout << Loop(N-1, M-1) << endl;
}

buttercrab 6년 전 0

두가지 요인이 있는데요,

먼저 그 장소의 값이 0이 된다면 다시 그 장소를 탐색할때 처음부터 탐색을 하게 됩니다. 따라서 처음 초기화를 -1로 하여 0과 헷갈리지 않도록 해야 합니다

두번째로는 cin cout이 느리기 때문인데요. ios_base::sync_with_stdio(false); 와 cin.tie(0); 을 써주어 시간초과를 막을수 있습니다.

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

문제

문제

출처

ICPC

시간초과

xotmd17 6년 전 0

buttercrab 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말