땅따먹기 자바스크립트

function solution(land) {
    
    for(let i = 1; i< land.length; i++) {
        land[i][0] += Math.max(land[i-1][1], land[i-1][2], land[i-1][3]);
        land[i][1] += Math.max(land[i-1][0], land[i-1][2], land[i-1][3]);
        land[i][2] += Math.max(land[i-1][0], land[i-1][1], land[i-1][3]);
        land[i][3] += Math.max(land[i-1][0], land[i-1][1], land[i-1][2]);
    }
    
    return Math.max(...land[land.length-1])
}



열의 개수가 많을 경우 반복문으로 처리.
function solution(land) {
    
    for(let i = 1; i< land.length; i++) {
        
        for(let j = 0; j< land[0].length; j++) {
            land[i][j] += Math.max(...land[i-1].filter((e,index) => index!== j))
        }
    }
    
    return Math.max(...land[land.length-1])
}

무조건 처음 행부터 최대값을 구해서 더할 경우 올바른 답이 나오지 않는다. 같은 열에 최대값이 몰려 있는 경우만 생각해봐도 문제가 복잡해지기 시작한다.

위 풀이 방법은 각 열마다 이전행 + 현재 행의 가능한 최대값을 갱신하면서 마지막 행까지 더해준 다음 그 중 최대값을 반환하는 방법이다.

열의 개수가 많아지게 된다면 위 반복문으로 처리해 볼 수 있는데 속도는 약 5배정도 느려진다. 필터메소드로 겹치는 인덱스를 찾아 제거해주는 과정에 시간을 많이 소요하기 때문인것 같다.