[Algorithm] 땅따먹기

문제설명

땅따먹기는 같은 열을 피해 행을 내려가며 가장 큰 수들의 합을 구하는 문제이다. 같은 열을 밟지 못한다는 규칙이 낮설어서 어떤 식으로 문제를 접근해야 할지 고민하게 되어 난이도가 많이 올라갔다.

문제해결

처음에는 첫번째 인덱스 [0,0]부터 [land.length -1, 3]까지 각 행을 더한 경우의 수를 구한 후 가장 큰 수를 반환해야겠다고 생각한 후 문제를 풀어나갔는데 열이 일치하지 않는 조건을 부여하는 과정에서 코드 작성이 막혀버렸다.

function solution(land) {
    // let total = 0;
    const width = lend.length;
    const height = lend[0].length;
    const visited = new Array(width).fill(false).map(e => new Array(width).fill(false));
    function dfs (x, y) {
        // 탈출문
        if (x >= width - 1 && y >= height - 1) return;
        if ()
    }
 }

다시 의사코드를 작성한 문제 해결에 대해 그림으로 시뮬레이션을 그려봤다.

• land의 두번째 행부터 순회하며 같은 열을 제외한 이전 행의 최대값을 찾아 더해준다.
• land의 마지막 행의 최대값을 반환한다.
  

파라미터로 주어진 land 배열을 직접 변경하여 메모이제이션으로 사용하면 불필요한 반복을 피할 수 있다.

다음은 표를 코드로 표현한 것이다.

function solution(land) {
    for (let i = 1; i < land.length; i++) {
        for (let j = 0; j < 4; j++) {
            //두번째 행부터 같은 열이 아닌 숫자의 가장 큰 수를 구하여 더한다.
            land[i][j] += Math.max(...land[i - 1].filter((_,idx) => idx !== j));
        }
    }
    // 마지막 행의 가장 큰 수를 반환한다.
    return Math.max(...land[land.length - 1])
}