kimgs0725   1년 전

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

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

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

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

haja   1년 전

그래프가 DAG가 아니라면 DP로 풀 수 없을 것 같습니다.

kimgs0725   1년 전

무슨 의미인지 알려주시면 감사하겠습니다.

haja   1년 전

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

kimgs0725   1년 전

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

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