[JS] 땅따먹기

 

 

난이도: Lv. 2

정답률: 58%

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

프로그래머스

 

 

알고리즘

1. 생성된 2차원 배열에서 열별 최댓값을 추출하여 1차원 배열을 생성한다.

2. 생성한 1차원 배열과 다음 행에 대해 1.의 과정을 수행한다. 모든 행에 대해 수행했다면 마지막 1차원 배열에서의 최댓값이 이 문제의 정답이 된다. 참고로 1차원 배열에는 각 행의 각 열까지 오는 경로 중 최댓값만 담기게 된다.

 

 

코드

function solution(land) {
    const col = 4;
    let level = 0;
    let currArr = [...land[0]];
    const D = Array.from({ length: 4 }, () => Array.from({ length: 4 }, () => 0));

    while (level < land.length - 1) {
        for (let i = 0; i < col; i++) {
            for (let j = 0; j < col; j++) {
                if (i === j) { D[i][j] = i; }
                else { D[j][i] = currArr[i] + land[level + 1][j]; }
            }
        }

        level++;
        currArr = [];
        for (let i = 0; i < col; i++) {
            currArr.push(Math.max(...D[i]));
        }
    }

    return Math.max(...currArr);
}

 

 

주저리

1트에는 dfs로 풀었는데 풀면서도 이거 백퍼 시간초과 난다 했는데 당연히 시간초과 났고, 2트에는 그리디로 풀었는데 다 틀려서 질문하기 염탐했는데 DP로 푸는 거라길래 한 번은 DP인척 하는 그리디로 잘못 풀어서 틀리고 두 번째에는 맞았다. DP 문제 푼 지 어언 2년 전이라 고민을 좀 오래 했다. 이 문제 푸는 데 걸린 시간은 총 1시간 정도인 것 같긴 한데 DP로 푸는 문제인 줄 몰랐다면 한참 더 걸렸을 것 같다.