17090 미로탈출

브루트포스 가정 하에 시간복잡도를 계산하면

O(N*M*(N+M)) N,M 제한이 500까지므로 2억이 넘는 값이 나온다. 1억 = 1초라는 기본 식에서는 불안한 값이다.

따라서 브루트포스 + dp를 적용해 O(N+M)을 O(1)로 줄여본다.

 

문제: https://www.acmicpc.net/problem/17090

https://github.com/surinoel/algorithm/blob/master/17090.cpp