[백준 - 2169] 로봇 조종하기

로봇은 아래, 왼쪽, 오른쪽으로 움직일 수 있지만 위로는 갈 수 없다. 같은 행에서 왼쪽과 오른쪽을 모두 허용하면 단순한 한 방향 DP만으로는 이전 칸을 다시 밟는 문제가 생긴다.

그래서 매 행마다 두 값을 따로 계산했다.

leftToRight[x] = max(previousRow[x], leftToRight[x - 1]) + value
rightToLeft[x] = max(previousRow[x], rightToLeft[x + 1]) + value
dp[x] = max(leftToRight[x], rightToLeft[x])

한 행을 양방향으로 훑으면, 현재 행에서 어느 방향으로 들어왔는지에 따른 최댓값을 각각 보존할 수 있다. 이전 행 값은 dp 하나만 유지해 메모리도 줄였다.

문제: 2169 로봇 조종하기 · 코드: GitHub에서 보기