글 읽기 - 이 문제 DP로도 풀 수 있지 않나요??

kimgs0725 7년 전 0

문제를 추상화 해보시면 결국 "목적지까지 가는데 최소한의 비용으로 가라"라고 해석이 됩니다.

그래서, d[y][x]를 "(y, x)에서의 최소비용"이라고 정의하고 풀었는데, 틀렸다고 나옵니다.

어디가 잘못됐는지 알려주시면 감사하겠습니다.

p.s 어떻게 다익스트라로도 풀 수가 있죠?

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int a[126][126], d[126][126], n;
const int dy[4] = { -1, 1, 0, 0 };
const int dx[4] = { 0, 0, -1, 1 };
const int INF = 987654321;
int move(int y, int x) {
	if (y == n - 1 && x == n - 1) return a[y][x];
	int& ret = d[y][x];
	if (ret != -1) return ret;
	ret = INF;
	for (int i = 0; i < 4; ++i) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (0 <= ny&&ny < n && 0 <= nx&&nx < n) {
			ret = min(ret, move(ny, nx) + a[y][x]);
		}
	}
	return ret;
}

int main(void) {
	int cnt = 1;
	while (true) {
		scanf("%d", &n);
		if (n == 0) break;
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < n; ++j)
				scanf("%d", &a[i][j]);
		memset(d, -1, sizeof(d));
		printf("Problem %d: %d\n", cnt++, move(0, 0));
	}
	return 0;
}

만약에 이 문제에서, 오른쪽 또는 아래로만 움직일 수 있다는 제약이 있다면, 그래프가 DAG가 되고 DP로 풀 수 있어요. 그런데 그래프에 사이클이 있을때 DP를 적용하면, 어떤 상태에서 무엇을 먼저 계산해야 할지 결정 할 수가 없어요. 저런식으로 함수를 짜면, 이 상태를 방문했다고 표시를 해서 무한 재귀를 돌진 않겠지만, 테이블에 틀린 값이 들어갈 수 있어요.
만약에 이 문제를 DP로 풀려고 하면 dp[x][y][k] : 0, 0에서 시작해서 x, y까지 k번 움직여서 갔을 때의 최소비용 이런식으로 정의를 해야 구할 수 있을거에요. 그런데 이렇게 정의하면 시간 복잡도가 O(n^4)가 되겠죠

kimgs0725 7년 전 0

아 그런 뜻이었군요. 감사합니다.

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

문제

문제

출처

ICPC

이 문제 DP로도 풀 수 있지 않나요??

kimgs0725 7년 전 0

haja 7년 전 0

kimgs0725 7년 전 0

haja 7년 전 5

kimgs0725 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말