발을 옮기는데 드는 비용이 정의되어 있다. (제자리에서 누르기 : 1, 중앙에서 이동해서 누르기 : 2, 대각선으로 이동해서 누르기 : 3, 가로질러 이동해 누르기 : 4) 주어진 입력을 모두 누르기 위해서는 발을 옮겨가며 해당 버튼을 누르게 될 텐데, 이때 주어진 입력을 모두 누르기 위한 최소 비용을 계산하라.
왼발과 오른발의 위치는 각각 5개의 상태 (가운데, 상, 하, 좌, 우)가 될 수 있다.
즉 두 발의 상태는 5x5 배열에 정의될 수 있다.
그것을 나타낸 것이 위의 이미지이다. 예를 들어 배열의 가로로 2번째, 세로로 3번째 칸은 오른발이 왼쪽 버튼을, 왼발이 아래쪽 버튼을 누른 상태를 의미하며, 그 값은 그 상태에 도달하기 위한 힘을 의미한다. (-1은 현재 그 상태에 없음을 의미한다.)
설명이 조금 복잡할 수 있으나, 위의 이미지를 보면 어떤 느낌인지 알 수 있을 것이라 생각한다. 이 5x5 DP 테이블을 이용해 문제를 풀어보자.
규칙은 아래와 같다.
규칙 A : "이번 상태 배열"에서 값이 -1이 아닌 모든 상태를 대상으로, 이번 입력을 수행했을 때의 상태와 비용을 "다음 상태 배열"로 옮긴다.
규칙 B : 규칙 A 종료 후, "이번 상태 배열"과 "다음 상태 배열"을 교환한다.
규칙 C : 규칙 A와 B를 반복하여 모든 입력을 종료한 뒤, 남아있는 배열에서 가장 작은 값을 출력한다.
이번 상태 배열 : 처음 시작할 때 양 발이 0,0에 존재한다. 첫 번째 커맨드인 1이 들어오면 오른발, 왼발 중 한 개를 1 지점으로 옮긴다. 이때 둘 다 중앙에서 이동하므로 [0,1] 상태와 [1, 0] 상태는 모두 [0, 0]의 비용 + 2이다.
이것을 다음 상태 배열에 저장한다.
다음 상태 배열: 다음 상태 배열에서는 [0,0] 상태가 존재하지 않으므로 (1,0 이거나 0,1이다.) [0, 0]의 값은 -1이 되어야 한다.
이후 이번 상태 배열과 다음 상태 배열을 교체한다.
이번 상태 배열:
입력이 2가 들어왔으므로 오른발, 왼발 중 하나를 2번 버튼으로 옮겨야 한다. 여기서 파란 화살표는 왼발을 옮기는 케이스이다.
[0, 1]에서 [0, 2]로 이동한 파란 화살표는 첫 명령을 왼발로 밟은 뒤, 이번 명령도 왼발로 밟는 것을 의미하며. 이는 왼발이 대각선 이동을 했으므로 비용 3짜리 이동을 하는 경우를 나타낸다.
[1, 0]에서 [1, 2]로 이동한 파란 화살표는 첫 명령을 오른발로 밟은 뒤, 이번 명령은 왼발로 밟는 것을 의미하며. 이는 오른발이 중앙에서 이동했으므로 비용 2짜리 이동을 하는 경우를 나타낸다.
빨강은 파랑과 대칭되는 이동이다.
다음 상태 배열:
이번 상태 배열: 다시 한번 2 입력이 들어왔다. 이때 [0,2], [2,0]에서 시작해 [2,2]로 오는 화살표는 각각 중앙에 있던 발을 옮겨 양발 다 2번 버튼 위로 올라오는 상황을 나타낸다.
[2,1], [1,2]의 원은 현재 2번 버튼 위에 위치하던 발을 이용해 한번 더 2번 버튼을 누르는 것을 의미한다.
다음 상태 배열:
이번 상태 배열:
입력이 4가 들어왔다. 각각의 상태에서 4번 버튼으로 가는 비용을 계산할 수 있다.
하지만 이번엔 특이하게 [2,4] 지점과 [4,2] 지점으로 가는 방법이 각각 2개씩 존재한다. 이 [2,4] 지점을 기준으로 보면 [2,2] 지점에서 [2,4]로 가는 경우와, [2,1] 지점에서 [2,4] 지점으로 가는 방법이 존재한다.
이 둘의 비용을 비교하면 8과 10으로 8이 더 싸다. 그러므로 다음 상태 배열은 아래와 같게 된다.
