프로그래머스 땅따먹기 - 자바스크립트 풀이(Bottom-up DP사용)

프로그래머스

 

문제 설명

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,
| 1 | 2 | 3 | 5 |
| 5 | 6 | 7 | 8 |
| 4 | 3 | 2 | 1 |
로 땅이 주어졌다면,
1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.
마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요.
위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

제한사항
행의 개수 N : 100,000 이하의 자연수열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.점수 : 100 이하의 자연수

입출력 예
land: [[1,2,3,5],[5,6,7,8],[4,3,2,1]]   → 결과: 16

 

동적계획법(Dynamic Programming) Bottom-up 방식을 채택해서 문제를 풀어보았다.

처음엔 동적계획법을 사용하지 않고 무작정 코드를 작성했더니 시간 초과라는 쓴 맛을 보았다. 😢

문제 풀이

위 그림은 각 요소 자리에 도달했을때 까지의 가장 큰 점수의 값을 담는 memo와 문제에 주어진 land이다.

동적계획법에서는 메모이제이션(memoization)으로 불필요하게 중복되는 계산을 줄인다.

2행 1열에 도달했을 때 가장 큰 점수를 구해보자. 2행 1열의 값인 5에 1행 4열의 값인 5가 합쳐졌을 때의 점수가 가장 크다.

그에 따라 2행 1열의 memo값은 10이 된다.

같은 방식으로 2행 4열에 올 수 있는 가장 큰 점수를 구하면

1행에서 가장 큰 점수인 5점은 2행 4열과 같은 4열이므로 선택이 불가능하다. 따라서 5점 다음으로 큰 1행 3열의 3점을 2행 4열의 점수와 합쳐준 값을 2행 4열의 memo값으로 할당한다.

이 같은 방식을 각 행과 열마다 반복하며 각 행, 열에 올 수 있는 가장 큰 점수를 구해나간다.

이를 코드로 구현하면 다음과 같다.

코드 

function solution(land) {
    let answer = 0, row = 1;
    const memo = Array.from({ length: land.length }, () => Array(4).fill(-1));

    memo[0] = land[0];
    
    while(row < land.length){
        for(let i = 0; i < 4; i++){
            for(let j = 0; j < 4; j++){
                if(j !== i && memo[row][i] < (land[row][i] + memo[row-1][j])) memo[row][i] = land[row][i] + memo[row-1][j];
            }
        }
        row++;
    }
    return Math.max(...memo[memo.length - 1]);
}

 

const memo = Array.from({ length: land.length }, () => Array(4).fill(-1));

행의 각 요소들 값이 -1로 초기화된 memo 변수를 정의한다.

이때, 1행은 결국 land의 1행과 똑같으므로

memo[0] = land[0];

이렇게 1행에 대한 값을 설정해준다.

while(row < land.length){
        for(let i = 0; i < 4; i++){
            for(let j = 0; j < 4; j++){
                if(j !== i && memo[row][i] < (land[row][i] + memo[row-1][j])) memo[row][i] = land[row][i] + memo[row-1][j];
            }
        }
        row++;
    }

그 후, 위에서 우리가 본 방식대로 각 행열에 올 수 있는 가장 큰 점수를 구해낸다.

return Math.max(...memo[memo.length - 1]);

마지막 행의 값들 중 가장 큰 값을 반환하면 완성이다 🤓