[BOJ] 백준 16720 BAZE RUNNER

문제 링크

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

가장 왼쪽 위에서 출발해 오른쪽 밑으로 도착해야한다.

맨 윗줄과 아랫줄 사이에는 벽들이 있는데, 한 줄당 세 칸의 벽과 한 칸의 통로가 있으며, 한 줄을 통째로 밀어 통로의 위치를 이동시킬 수 있다.

간단하게 풀 수 있다.

우선 현재 위치에서 왼쪽 혹은 위로 가는 경로는 당연히 제외한다.

저 두 상황을 제외한다면 단순히 인접한 길로 이동하는 총 시간은 어떻게 가도 같게된다.

다음으로 어떤 벽을 어떻게 회전시킬지를 결정해야 한다.

통로의 위치를 한 열로 몰아준다.

생각하기 싫어서 1, 2, 3, 4번 열 모두 한 번씩 해본 뒤 가장 작은 값을 구했다.

답을 { 3 (오른쪽으로 이동) + (n - 1) (아래로 이동) + $\sum$ 벽 회전 횟수 } 로 구해줄 수 있다.

정답 코드