문제
- 시간 제한: 2초
- 메모리 제한: 256MB
Problem Analysis
답을 구하는 특별한 수식이 존재하지 않는다. 모든 칸을 조사해 보아야 하는데, 현재 칸에서의 최대는, 상하좌우 인접칸에서 시작할 때의 최대 + 1 이다. 즉, Sub-Problem이 반복되는 것이므로, Dynamic Programming으로 풀 수 있다.
Algorithm
- 현재 칸에서 이동 가능한 상하좌우 칸을 조사한다
- 이미 조사했다면, 저장된 값을 참조
- 그렇지 않다면, recursive call
- 조사한 상하좌우 칸의 최댓값 + 1을 현재 칸에 저장
- 조사하지 않은 칸이 있다면, 1로 돌아가 조사
Data Structure
- forest[n][n]: 대나무 숲 저장
- dp[n][n]: 각 칸의 최대 저장
결과
Other
시간 복잡도는 DFS가 O(V+E)이므로, O(N^2)이다.
