격자형DP

백준 2169번(로봇 조종하기)은 단순한 DP처럼 보이지만, 한 행에서 양방향 이동이 가능하다는 조건 때문에 순환 참조(Circular Dependency) 문제가 발생합니다. 본 리포트에서는 O(NM²)의 비효율적인 접근이 왜 운 좋게 통과되었는지 분석하고, 이를 O(NM)으로 최적화하기 위한 ‘Directional Split DP(방향 분리 DP)’ 기법을 심층적으로 다룹니다. 좌/우 스캔을 통해 DP의 핵심 전제인 DAG(Directed Acyclic Graph)를 어떻게 복원하는지 상세히 설명합니다.