[BOJ] 2169 - 로봇 조종하기

BOJ 2169 - 로봇 조종하기 (https://www.acmicpc.net/problem/2169)

요즘 DP 문제 푸는게 재밌어서 자주 풀고 있다.

여전히 어렵긴 어려운데, 예전보다는 감각이 생겨서 그런가보다. 이번에는 아는 동생에게 추천 받은 문제를 풀어보았다.

풀이 및 유의할 점

이 문제는 DFS DP로 풀면 되는데, 주의할 점이 있다.

• 배열에는 음수도 있음 (배열 전체가 음수인 케이스까지도 당연히 고려해야함)
  • 나같은 경우는 넉넉하게 초기화 값을 -1000000으로 줬다.

• 한번 내려오면 위로 올라갈 수 없음 (그냥 visit 체크만 잘 해주면 됨)

• 마지막 줄에서 막다른 길로 갈 때의 케이스를 고려해야함
  • 예를 들면, 마지막 줄에서 왼쪽으로 쭉 가서 (N, 0)에 도달하는 케이스가 있겠다.

처음에는 DP 배열을 아래와 같이 설계했고, 덕분에 한시간 넘게 헤맸다.

DP[i][j][dir] = 현재 (i,j)번째에 있고 이전 index에서 온 방향이 dir일 때의 최대값

깊게 생각하지 않고 설계를 이렇게 했다는 것은 아직까지 내 실력이 부족하다는 증거인데, 다행히 이렇게 짜면 답을 낼 수 없다는 것을 깨닫고 아래와 같이 바꾸었다.

DP[i][j][dir] = (i,j)번째에서 탐색을 시작하여 dir 방향으로 진행했을 때 얻을 수 있는 최대값

이렇게 하면 추후 다른 케이스를 통하여 (i,j) 번째에 도달 했을 때 dir 방향으로 또 탐색하는 것이 아니라, 이미 저장되어 있는 값을 토대로 최대값을 찾게 되니 시간 제한내로 통과할 수 있다.

탐색의 경우 위로 올라갈 수 없게 되어있으니 케이스는 3개 (왼쪽, 오른쪽, 아래)만 고려하면 되며, 마지막 줄에 도달했을 때는 왼쪽으로 가지 않도록 해주면 좋다.

위에 명시한 것처럼, DP 배열에는 현재 위치에서 탐색을 시작하여 얻을 수 있는 최대값을 저장하는 것이기 때문에 출력해야 되는 정답은 DP[0][0][0..2] 중에 있다.
나같은 경우 dir을 0 : 왼쪽, 1 : 아래쪽, 2 : 오른쪽으로 놓고 풀었고 첫번째 칸에서 왼쪽으로 갈 수 있는 방법은 없으니 max(DP[0][0][1], DP[0][0][2])를 출력해주면 되었다.

전체 코드