문제
NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만, 로봇의 메모리가 얼마 안 되기 때문에 지형을 N×M 배열로 단순화 하여 생각하기로 한다.
지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다. 또한 한 번 탐사한 지역(배열에서 하나의 칸)은 탐사하지 않기로 한다.
각각의 지역은 탐사 가치가 있는데, 로봇을 배열의 왼쪽 위 (1, 1)에서 출발시켜 오른쪽 아래 (N, M)으로 보내려고 한다. 이때, 위의 조건을 만족하면서, 탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오.
입력
첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다.
출력
첫째 줄에 최대 가치의 합을 출력한다.
예제 입력 1
5 5
10 25 7 8 13
68 24 -78 63 32
12 -69 100 -29 -25
-16 -22 -57 -33 99
7 -76 -11 77 15예제 출력 1
319풀이
로봇은 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있다.
위로는 이동할 수 없기 때문에 행은 위에서 아래로, 단방향으로 탐색한다.
한 번 탐사한 지역을 다시 방문하지 않기 때문에
한 행에서 왼쪽으로 이동을 시작했다면, 끝까지 왼쪽 방향으로만 이동한다.
행마다 왼쪽 끝과 오른쪽 끝에서 탐색을 시작하고 각 방향에서의 최대 가치를 구한다.
그럼 그 칸의 최대 탐사 가치는 오른쪽으로 이동할 때의 최댓값과 왼쪽으로 이동할 때의 최댓값 중 큰 값이 된다.
모든 행에 대해 이를 수행하면 (N, M) 칸에 최대 가치를 구할 수 있다.
코드
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [n, m] = input.shift().split(" ").map(Number);
const board = Array.from({length:n}, (v, i) => input[i].split(" ").map(Number));
const L_INF = Number.MIN_VALUE;
// worth[i][j] : (i, j)에서의 최대 가치
const worth = Array.from({length:n}, () => Array(m).fill(0));
// 탐색 시작 행 초기화
worth[0][0] = board[0][0];
for (let j=1; j<m; j++) worth[0][j] = worth[0][j-1] + board[0][j];
for (let i=1; i<n; i++) {
let move2right = Array(m).fill(L_INF); // 오른쪽으로 이동할 때의 최대 가치
let move2left = Array(m).fill(L_INF); // 왼쪽으로 이동할 때의 최대 가치
// 시작 칸 초기화
move2right[0] = worth[i-1][0] + board[i][0];
move2left[m-1] = worth[i-1][m-1] + board[i][m-1];
for (let j=1; j<m; j++) move2right[j] = Math.max(worth[i-1][j], move2right[j-1]) + board[i][j]; // 위에서 아래로 이동했을 때와 오른쪽으로 이동했을 때의 가치 비교
for (let j=m-2; j>=0; j--) move2left[j] = Math.max(worth[i-1][j], move2left[j+1]) + board[i][j]; // 위에서 아래로 이동했을 때와 왼쪽으로 이동했을 때의 가치 비교
for (let j=0; j<m; j++) worth[i][j] = Math.max(move2right[j], move2left[j]);
}
console.log(worth[n-1][m-1]);