진우의 달 여행 (Small)
면접 대비시간 제한1초메모리 제한256 MB
각 칸에 연료 소모량이 적힌 N X M 격자(N, M은 6 이하)에서 첫째 행 아무 칸에서 시작해 마지막 행 아무 칸에 도착하는 최소 연료 경로를 구한다. 매 이동은 아래 방향으로 진행하며 같은 방향을 연속해서 두 번 쓸 수 없다.
문제
우주비행이 꿈이었던 진우는 음식점 '매일매일싱싱'에서 열심히 일한 끝에 달 여행에 필요한 자금을 모두 모았다. 지구와 달 사이의 공간은 N X M 행렬로 나타낼 수 있고, 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다.
[예시]
진우는 여행 경비를 아끼려고 조금 특이한 우주선을 골랐다. 진우가 고른 우주선의 특징은 다음과 같다.
1. 지구에서 달로 갈 때 우주선이 움직일 수 있는 방향은 아래와 같다.
2. 우주선은 직전에 움직인 방향으로 움직일 수 없다. 즉, 같은 방향으로 두 번 연속 움직일 수 없다.
진우의 목표는 연료를 최대한 아끼며 지구의 어느 위치에서든 출발해 달의 어느 위치든 착륙하는 것이다.
돈을 아끼며 달에 도착하고 싶은 진우를 위해, 달에 도달하는 데 필요한 연료의 최솟값을 계산하자.
입력
첫 줄에 지구와 달 사이 공간을 나타내는 행렬의 크기 N, M (2≤ N, M ≤ 6)이 주어진다.
다음 N줄에 걸쳐 행렬의 원소 값이 주어진다. 각 원소 값은 100 이하의 자연수이다.
출력
달 여행에 필요한 최소 연료의 값을 출력한다.