글 읽기 - DP로 푼게 아닌가요???

bhw0506 8년 전 0

나름 DP로 풀어 볼려고 풀어 보았는데

이게 시간초과가 뜨네요 ㅜ

이게 DP로 짠게 맞나여?

//============================================================================
// Name        : 1520.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

int A[500][500];
int DP[500][500];

int N, M;
int result = 0;

int Ans(int a, int b) {

	if(a >= N || b >= M) return 0;

	if(a == N - 1 && b == M - 1) {
		result++;
		return 1;
	}

	int up = 0, down = 0 , left1 = 0 , right1 = 0;

	int val = A[a][b];

	if(val > A[a+1][b]) {
		down = Ans(a+1, b);
		if(DP[a][b+1] == 0 && DP[a-1][b] == 0 && DP[a][b-1] == 1) return 0;
	}

	if(val > A[a][b+1]) {
		right1 = Ans(a, b+1) ;
		if(DP[a-1][b] == 0 && DP[b] == 0) return 0;
	}

	if(val > A[a-1][b]) {
		up = Ans(a-1, b);
		if(DP[a][b-1] == 0) return 0;
	}

	if(val > A[a][b-1]) left1 = Ans(a, b-1);


	return DP[a][b] = up || down || left1 || right1;
}
int main() {

	cin >> N >> M;
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < M; j++) {
			cin >> A[i][j];
			DP[i][j] = -1;
		}
	}
	Ans(0, 0);
	cout <<result;

	return 0;
}

yukariko 8년 전 0

dp는 중복되는 부분문제를 재계산하지않기 위한 테크닉인데,

위 소스는 dp가 ans(a,b)의 부분문제를 대변하지 않고 단순 가지치기로 작용하고 있는것 같습니다.

dp[a][b] 가 ans(a,b)의 답을 대신해준다고 생각하고 다시 코드를 작성해보세요.

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

문제

문제

출처

ICPC

DP로 푼게 아닌가요???

bhw0506 8년 전 0

yukariko 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말