algospot   10달 전

이 문제의 맞은 사람 99.9%가

재귀다이나믹으로 풀었는데 혹은, BFS , DFS

그런데 문제의 입력이 500x500이고 종료조건이 (N-1,M-1 ; 즉 하나의 정점)으로 정해져있습니다.

이 문제에서 입력이 가령, 500x500이고 지그재그로 모든 정점을 방문해야할 경우 250000개의 스택이 쌓입니다.

그렇다면 문제의 답이 구해지기 전에 스택오버플로우로 닫히게 되겠죠.

즉, 다시 말해 문제의 입력이 그러한 경우가 주어지지 않아 (저같은 경우도 마찬가지로) 정답으로 되었는데,

500x500으로 책정했다는 것은 최악의 경우도 돌아가게 된 배열 다이나믹을 원하는 문제인거같습니다.

배열 다이나믹으로 풀이를 어떻게 해야할까요?

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