프로그래머스 땅따먹기 JavaScript
2022년 12월 23일
제한 사항
- 행의 개수 N: 100,000이하의 자연수
- 열의 개수는 4개, 땅(land)은 2차원 배열로 주어집니다.
- 점수: 100 이하의 자연수
입출력 예
| land | answer |
|---|---|
| [[1,2,3,5],[5,6,7,8],[4,3,2,1]] | 16 |
문제 풀이
행렬 (i, j) 자리의 최댓값은 dp 행렬 (i-1, ( j 열을 제외한 나머지 열 ))들 중에 최댓값에서 내려갈 때이다.
| i-1, a | i-1, b | i-1, c | i-1, d |
| i, a | i, b | i, c | i, d |
| i+1, a | i+1, b | i+1, c | i+1, d |
(i+1, b) 자리의 최댓값은 dp 행렬 (i, a), (i, c), (i, d) 중 최댓값에서 행렬(i+1, b) 값을 더한 값이 된다.
점화식
(a, b, c, d : 0~3)
j 가 a 일 때:
dp[i][j] = max(dp[i-1][b], dp[i-1][c], dp[i-1][d]) + arr[i][j]
solution.js
function solution(land) {
let answer = 0;
const rowLength = land.length;
const colLength = 4;
const dp = Array.from(Array(rowLength), () => new Array(4));
dp[0] = [...land[0]];
for (let i = 1; i < rowLength; i++) {
for (let j = 0; j < colLength; j++) {
let MAXNUM = 0;
for (let k = 0; k < colLength; k++) {
if (j !== k && MAXNUM < dp[i-1][k]) {
MAXNUM = dp[i-1][k];
}
}
dp[i][j] = land[i][j] + MAXNUM;
}
}
answer = Math.max(...dp[rowLength-1]);
return answer;s
}