[Algorithm] 프로그래머스 - 땅따먹기 (JS)

문제

총 N행 4열로 이루어진 땅에서, 1행 부터 한 행씩 한 칸만 밟으며 내려왔을 때 얻을 수 있는 최고점을 리턴하는 문제. 단, 같은 열은 밟을 수 없는 특수한 규칙이 있다.

문제 링크

입출력 예시

let output1 = solution([[1,2,3,5],[5,6,7,8],[4,3,2,1]]); // -> 16
console.log(output1);

처음에는 문제를 제대로 이해하지 못해서 첫 번째 행부터 가장 큰 수만 고르면 되는 문제인 줄 알았다. 문제는 행과 상관없이 주어진 땅 전체에서 정해진 규칙에 따라서 얻을 수 있는 최고점을 묻는 문제였다..

예를 들어, 두 번째 행의 8을 10으로 바꿨을 때 10을 선택해야 가장 큰 수가 나오기 때문에 첫 번째 행은 그 행에서 두 번째로 큰 수인 3을 선택해야한다.

---

풀이 방법

앞서 설명한 듯이, 반복되는 행에서 무조건 가장 큰 수를 선택할 수 없다.
핵심은 i - 1의 행과 i의 행을 같이 보면서, 가장 큰 수의 조합을 찾는 것이다.
코드와 함께 그림을 보면 이해하기 좀 더 쉬울 것이다.

...
land.forEach((row, i) => {
        // 0번째 행은 스킵
        if (i === 0) return;
        row.forEach((_, j) => {
            // 이전 행을 복사한다
            const copyRow = land[i - 1].slice();
            // 각 행의 수를 가장 작은 자연수 0으로 만들어준다
            copyRow[j] = 0;
            // copyRow 중 가장 큰 수를 누적시켜서 land에 할당한다
            land[i][j] += Math.max(...copyRow);
        })
...

같은 열은 선택할 수 없는 규칙이 있기 때문에, 각 요소를 0을 만든 후 최고점을 구한다.

그리고 최고점을 다음 행 같은 열에 누적시킨다. 이 과정을 끝까지 반복하면 된다.

마지막에 행이 모든 점수가 누적된 결과가 되고, 그 중 가장 큰 값을 리턴해주면 된다.

...
// 점수가 누적된 마지막 행에서 가장 큰 수를 리턴
return Math.max(...land[land.length - 1])

이렇게 완성된 코드는 다음과 같다.

function solution(land) {
    land.forEach((row, i) => {
        if (i === 0) return;
        row.forEach((_, j) => {
            const copyRow = land[i - 1].slice();
            copyRow[j] = 0;
            land[i][j] += Math.max(...copyRow);
        })
    })
    return Math.max(...land[land.length - 1])
}