[Javascript/자바스크립트] (프로그래머스) 땅따먹기

https://school.programmers.co.kr/learn/courses/30/lessons/12913

코드

function solution(land) {
    let answer = 0;
    const n = land.length;

    const dp = Array.from(new Array(n), ()=>new Array(4).fill(0));
    for(let i = 0;i < 4;i++){
        dp[0][i] = land[0][i];
    }

    // DP
    for(let i = 1 ; i < n ; i++){
        for(let j = 0;j<4;j++){
            for(let k=0;k<4;k++){
                if(j==k) continue;
                dp[i][j] = Math.max(dp[i-1][k]+land[i][j], dp[i][j]);
            }
        }
    }

    answer = Math.max(...dp[n-1]);
    return answer;
}

 

땅따먹기는 행을 하나씩 차례로 밟으면서 내려와야 한다. 그 말은 k번째 행으로 오기 위해서는 k-1행을 무조건 거쳐야 한다는 말이다. 이런 경우에는 이전에 저장된 값을 이용하여 연산 횟수를 줄이는 DP(Dynamic Programming)을 사용하면 시간 복잡도를 작게 만들어서 풀 수 있다.

 

2차원 배열 `dp`는 땅(land)의 각 칸까지 도달했을 때 얻을 수 있는 점수의 최고점을 저장하기 위한 배열이다. 그러니까 `dp[i][j]`는 0행부터 밟으면서 내려와서 (i,j)까지 도달했을 때 얻을 수 있는 최고점이 저장된다.

 

DP 과정은 어렵지 않다. 1행부터 n-1행까지 한 줄씩 dp 배열의 값을 채워나가면 된다. 이때 사용할 수 있는 점화식은 다음과 같다.

0번째 행은 이전 줄이 없기 때문에 land 배열의 같은 위치의 값을 그대로 저장해준다. 그리고 1번째 행부터는 이전 행에서 자신과 같은 열은 제외하고 최대값을 구해서 그 값과 `land[i][j]`를 더한 값을 `dp[i][j]`에 저장하는 것이다.

 

이를 코드로 나타내면 아래와 같이 구현할 수 있다.

for(let i = 0;i < 4;i++){
        dp[0][i] = land[0][i];
    }

// DP
for(let i = 1 ; i < n ; i++){
    for(let j = 0;j<4;j++){
        for(let k=0;k<4;k++){
            if(j==k) continue;
            dp[i][j] = Math.max(dp[i-1][k]+land[i][j], dp[i][j]);
        }
    }
}