[Javascript] 땅따먹기 (12913)

문제링크

코딩테스트 연습 - 땅따먹기

 

N행 4열로 이루어진 배열이 주어지고 각 요소마다 점수가 주어질 때
행마다 하나의 값씩 더해 가장 큰 값을 출력하는 문제이다.

조건 : 연속된 열로 이동할 수 없다.

접근 방법

이전 행의 가장 큰 값과 현재 행을 더하고, 현재행의 가장 큰값과 다음행을 더하면서 dp방식으로 접근하였다.

1 2 3 4       1  2   3   4
5 6 7 8 =>  9 10 11 11

코드의 핵심은 연속된 열의 값을 더 할 수 없으므로

land[row][col] += Math.max(...land[row-1].slice(0, col), ...land[row-1].slice(col+1))​

이전행의 열과 같은 열을 제외한 부분에서 Max값을 찾는 것이다.

function solution(land) {
    var answer = 0;
    
    for(let row = 1; row < land.length; row++){
        for(let col = 0; col < land[0].length; col++){
            land[row][col] += Math.max(...land[row-1].slice(0, col), ...land[row-1].slice(col+1))
        }
    }
    
    answer = Math.max(...land[land.length-1])
    
    return answer;
}