[프로그래머스] 땅따먹기 / Javascript

문제 설명

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(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	answer
[[1,2,3,5],[5,6,7,8],[4,3,2,1]]	16

풀이 과정

문제에서 주의해야 할 조건은 같은 열을 연속해서 밟을 수 없다는 것이다.
처음에는 연속해서라는 말을 못 보고 한 번 밟은 열은 다시는 못 밟는다고 생각하고 dfs를 이용해서 매번 다른 열을 밟았을 때의 최댓값을 구하도록 했다.
코드를 제출했더니 당연히 모든 테케를 다 틀렸다..^^...
행의 개수가 십만개가 될 수 있는데 열을 한 번만 밟는다는 것은 말이 안되지...
문제를 풀 때는 조건을 똑바로 제대로,,읽도록 하자..
연속해서 밟을 수 없다는 조건을 제대로 확인한 뒤에 다이나믹 프로그래밍을 이용해서 코드를 짰다.

제일 먼저, dp는 이차원 배열로 선언해줬다.

const dp = Array.from(Array(rowLength), () => Array(4).fill(0));

첫번째 행에서의 최댓값은 땅의 첫번째 행의 점수와 같기 때문에
dp의 첫번째 행은 땅의 첫번째 행의 값으로 변경해줬다.

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

그리고 두번째 행부터의 최댓값은 위 행의 최댓값에 자신의 점수를 더한 값이다.
하지만 같은 열을 연속해서 밟을 수 없기 때문에 위 행을 확인할 때 같은 열을 제외한
값들만 확인하도록 했다.

for(let i = 1; i < rowLength; i++) {
    dp[i][0] = Math.max(dp[i - 1][1], Math.max(dp[i - 1][2], dp[i - 1][3])) + land[i][0];
    dp[i][1] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][2], dp[i - 1][3])) + land[i][1];
    dp[i][2] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][1], dp[i - 1][3])) + land[i][2];
    dp[i][3] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][1], dp[i - 1][2])) + land[i][3];
}

이렇게 구한 dp의 마지막 행 중 최댓값이 정답이 된다.

for(let j = 0; j < 4; j++) {
    answer = Math.max(answer, dp[rowLength - 1][j]);
}

전체 코드는 다음과 같다.

const solution = (land) => {
    const rowLength = land.length;
    const dp = Array.from(Array(rowLength), () => Array(4).fill(0));
    let answer = 0;
    // 1행의 최대값은 land 1행이랑 값이 같음
    for (let j = 0; j < 4; j++) {
        dp[0][j] = land[0][j];
    }

    for (let i = 1; i < rowLength; i++) {
        // 연속으로 같은 열을 밟을 수 없기 때문에
        // 윗행의 dp 값에서 현재 열을 제외한 값들 중 최댓값과 land 값을 더한 놈으로 값을 변경해줌
        dp[i][0] = Math.max(dp[i - 1][1], Math.max(dp[i - 1][2], dp[i - 1][3])) + land[i][0];
        dp[i][1] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][2], dp[i - 1][3])) + land[i][1];
        dp[i][2] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][1], dp[i - 1][3])) + land[i][2];
        dp[i][3] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][1], dp[i - 1][2])) + land[i][3];
    }
    // 마지막 행의 dp 값 중 최대값을 answer에 대입
    for (let j = 0; j < 4; j++) {
        answer = Math.max(answer, dp[rowLength - 1][j]);
    }

    return answer;
}

풀이 결과