[DP] DDR

[문제 출처 : 하늘바다 컴퓨터 학원 수지점]

 

요즘 원장님의 고민은 뱃살을 뺴는 것이다. 친구에게 DDR게임을 하면 뱃살이 빠진다는 말을 듣던 그 날부터 DDR게임을

 

하루도 빼먹지 않고 열심히 하고 있다. 하지만 워낙 몸이 무거워 게임을 잘 하지는 못한다.

 

그럼에도 불구하고 원장님은 살을 뺄 수 있다는 일념으로 게임을 아주 열심히 하고 있다.

 

DDR게임의 게임판 모양은 아래 그림과 같다.

 

시작은 두발을 모두 중앙(0의 위치)에서 모으고 있다가 게임이 시작되면, 지시에 따라 왼쪽,또는 오른쪽 발을 움직인다. 

 

하지만 두 발이 동시에 움직이지는 못한다. 이게임에는 이상한 규칙이 하나 더있다. 시작할 때를 제외하고 두 발이 같은

 

지점에 있는 것을 허락하지 않는 것이다. 만약, 한 발이 1의 위치에 있고, 다른 한발이 3의 위치에 있을 때 3을 연속으로 눌러야 한다면, 3의 위치에 있는 발로 반복해 눌러야 한다는 것이다. 

 

원장님은 게임이 익숙해지자 발이 움직이는 위치에 따라서 다는 힘이 다르다는 것을 알게 되었다.

 

만약, 중앙에 있던 발이 다른 지점으로 움직일 때 2의 힘을 사용하게 된다.

 

그리고 다른 지점에서 인접한 지점으로 움직일 떄는 3의 힘을 사용하게 된다. (예를 들면 왼쪽에서 위나 아래로 이동할 때 이야기다)

 

그리고 반대편으로 움직일 떄는 4의 힘을 사용하게 된다. (위쪽에서 아래쪽으로, 또는 오른쪽에서 왼쪽으로)

 

만약 같은 지점을 한번 더 누른다면 그때는 1의 힘을 사용하게 된다. 게임의 정보가 주어질 때 원장님이 최소 얼만큼의 힘을 주어야 게임을 끝마칠 수 있는지 알려주는 프로그램을 작성하시오. 

 

[입력]

입력의 1행에는 밟아야하는 발판의 갯수가 주어진다.

2행부터는 밟아야하는 발판의 종류가 주어진다.

 

[출력]

발판을 모두 밟을 때 드는 최소힘을 출력한다.

 

입출력 예::

 

입력::

4

1 2 2 4

 

출력::

8

 

 

 

[풀이]

각 발판들이 주변으로 이어지는 비용을 표로 나타내면 다음과 같다.

 

0 2 2 2 2

2 1 3 4 3

2 3 1 3 4

2 4 3 1 3

2 3 4 3 1

 

점화식을 위해서는 주어진 각 노드들에 해당하는 테이블을 그리고 이전 테이블에서 얻은 값과 현재 이동해야하는 노드까지의 거리를 구하고 갱신해야할 것이다.

 

직접 예제 입출력을 가지고 진행해보자

 

우선 0번째 테이블이 있을 것이다. 0번 테이블은 아직 시작하기 전 초기값을 의미한다. 이 게임은 두발을 중앙 즉, 0번에 붙이고 시작하므로 0번 테이블 0, 0은 0이다. 

 

이후 주어진 첫 발판이 1번 발판이다. 1번 테이블을 모두 최댓값으로 채우고 다음 조건을 검사한다.

 

1.현재 테이블의 [이동해야하는 발판, j]값이 이전 테이블의 [i, j]값 + 비용표의 [이동해야하는 발판, j] 보다 크다면 현재 테이블 값 갱신

2.현재 테이블의 [i, 이동해야하는 발판]값이 이전 테이블의 [i, j]값 + 비용표의 [i, 이동해야하는 발판] 보다 크다면 현재 테이블 값 갱신

 

두 조건은 각각 왼발로 이동하는 경우와 오른발로 이동하는 경우를 의미한다.

 

for(i=1;i<=n;i++) {
    int now = arr[i];
    for(j=0;j<5;j++) {
        for(k=0;k<5;k++) {
            if(table[i][j][now] > table[i-1][j][k] + value[j][now]) {
                table[i][j][now] = table[i-1][j][k] + value[j][now];
            }
            if(table[i][now][k] > table[i-1][j][k] + value[now][k]) {
                table[i][now][k] = table[i-1][j][k] + value[now][k];
            }
        }
    }
}

 

이런 식으로 마지막 테이블까지 계산을 하고 답을 구한다.