글 읽기 - dp인데 대체 어디가 문제인지 모르겠습니다

Green55 6년 전 0

1시간 넘게 디버깅 해봤는데 어디가 문제인지 도저히 모르겠습니다.

solve(1,2,2)에서의 실제 최적은 d=0 일 때의 solve(2,2,0)을 택하는 것인데, solve(2,2,0)이 INF로 계산이 됩니다.

원래 solve(2,2,0)의 값은 9여야 하고, main에서 애초에 solve(0,0,0)을 호출하지 말고 처음부터 solve(1,2,2)를 호출하면 제대로 solve(2,2,0)을 9로 계산합니다. 문제의 원인이 뭘까요??

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
const ll INF = 11111100000;
int n, T, board[100][100];
ll dp[100][100][3];
ll solve(int x, int y, int cross){
	if(x == n-1 && y == n-1) return 0;
	ll &ret = dp[x][y][cross];
	if(ret != -1) return ret;
	ret = INF;
	for(int d=0; d<4; ++d){
		int nx = x+dir[d][0], ny = y+dir[d][1];
		if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
		if(cross == 2)
			ret = min(ret, board[nx][ny] + T + solve(nx, ny, 0));
		else
			ret = min(ret, T + solve(nx, ny, cross+1));
	}
	return ret;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> T;
	memset(dp, -1, sizeof(dp));
	for(int i=0; i<n; ++i)
		for(int j=0; j<n; ++j)
			cin >> board[i][j];
	cout << solve(0,0,0);
}

jwvg0425 6년 전 0

이런 문제의 경우 싸이클이 발생하기 때문에 DP로는 풀 수 없습니다(문제 x를 해결하기 위해 x의 부분 문제 y를 해결해야하는데, y의 답을 구하기 위해서는 다시 x가 필요한 경우가 발생하기 때문)

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

문제

문제

출처

ICPC

dp인데 대체 어디가 문제인지 모르겠습니다

Green55 6년 전 0

jwvg0425 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말