BOJ 1937 - 욕심쟁이 판다

문제 링크

---

https://www.acmicpc.net/problem/1937

문제 해결

---

 1. 상하좌우를 움직여서 현재보다 증가하는 방향으로 나아가는 가장 긴 거리를 구하는 문제.

 2. DP[i][j] = (i, j)에서 출발했을 때, 도달할 수 있는 가장 긴 거리.

주의할 점 || 생각해볼 점

---

 1. 주로 한 방향으로 증가하는 문제만이 DP라고 생각하기 쉽기 때문에, 상하좌우 움직이는 이 문제에 대해서 DP를 생각하기 쉽지가 않다.

 2. 하지만 어느 점에서 출발하든, (i, j)를 지나게되면 (i, j)로 부터 도달할 수 있는 최장 거리는 같게된다.

 3. 만약 그냥 DFS만을 사용하게되면 의 시간이 소요된다.(정점의 개수를 N*N이라하고 전체 다 이동한다 생각하면 N*N만큼 이동할 수 있으므로)

참고

---

 - 

※ 정확하고 부드러운 태클은 언제나 환영입니다.