문제

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

풀이

얻을 수 있는 점수의 최댓값을 찾아야 하는 문제다.

행을 한칸씩 내려오면서 해당칸의 값을 더하는 과정을 통해 최댓값이 구해진다.

문제 예시에 나온 3 * 4행렬을 봐보자. 2행 1열인 5가 써있는 칸을 밟는다고 한다면, 이 이전 행에서 무슨 값을 밟고 내려오면 5칸에서 최댓값이 될까?

5와 같은 열인 1을 제외하고, 2 + 5, 3 + 5, 5 + 5이렇게 세 개의 값을 비교해 제일 큰 값이 바로 밟고 온 칸이 된다. 최댓값이 10이므로 밟고온 칸은 5(1행 3열)이다.
그렇게 2행 나머지 열들(6, 7, 8)이 가질 수 있는 최댓값을 같은 방식으로 구할 수 있다.

어렵다면 아래 그림을 보면서 이해해보자.

만약 땅따먹기 게임이 land의 2행까지만 있다면, 1행에서 5, 2행에서 7을 밟아 최대값 12를 만들면 게임에서 이길 수 있다.

그런데 문제에서는 게임의 행 개수가 N으로 미지수다. 그럼 어떻게 해야할까?

발상을 바꿔보자.

우리가 1행에서 2행의 최댓값을 구한 것처럼 사실은 0행에서 1행의 최댓값이 구해졌다고 생각해보는 것이다.(1행1열이 1이니까 0행은 소수로 되어있겠죠?) 그렇다면 0행에서 구한 1행의 최댓값으로 2행의 최댓값인 12를 알게 된 것이다.

그렇다면, 2행을 N행이라고 생각해도 똑같아진다. N행에서의 최댓값은 N-1행의 최댓값을 통해 구해지고, N-1행의 최댓값은 N-2행의 최댓값을 통해 구해진다. 각 행의 최댓값을 구하는 과정은 앞의 사진처럼 간단하게 구할 수 있다. 같은 열을 제외하고 더한 값들의 최대값(Math.max())을 찾아주면 된다.

앞선 행의 최댓값을 구해 저장해놓고, 그 다음 행의 최댓값을 구하는데에 사용한다.
결론적으로 N행의 땅따먹기 게임의 결과는 1행부터 N행까지의 최댓값을 구해 저장하고 사용하는 과정의 연속으로 도출되게 된다.

피보나치와 비슷한 구조!

이해가 어렵다면 피보나치 수를 생각해보자. fibo(5)를 구하기 위해 fibo(4)와 fibo(3)이 필요하고, fibo(4)를 구하기 위해 fibo(3)과 fibo(2)가 필요하고.., 마찬가지로 N행의 최댓값을 구하기 위해 N-1행의 최댓값이 필요하고, N-1행의 최댓값을 구하기 위해 N-2의 최댓값이 필요하다. 이렇게 보니 둘은 매우 유사하다.

코드로 어떻게 작성해야할까? 직관적인 힌트

dp 배열 선언하기

위 구조를 코드로 작성하기 위해선 최댓값을 저장할 배열이 필요하다. 배열은 각 행의 모든 열의 구해진 최댓값을 저장해야하므로, 그냥 문제에서 주는 land 배열과 똑같은 크기의 2차원 배열로 선언하면 간단하다.

초기값 할당

생성한 배열에는 초기값을 줘야한다. 이 행을 기준으로 다음 행들의 최댓값들을 구해나갈 것이기 때문이다.

dp 배열 채우기

그리고 문제에서 같은 열을 연속해서 밟으면 안된다고 했으므로, 현재 열을 제외한 열들과 더해 최대값을 구하면 된다.

정답 코드

function solution(land) {
    return maxSum(land);
}

const maxSum = land => {
    const [row, col] = [land.length, land[0].length]; // 주어진 행렬의 행의 크기 row, 열의 크기 col
    
    const dp = Array.from(Array(row), () => Array(col).fill(0)); // 주어진 행렬과 똑같은 크기의 0으로 초기화된 배열 dp
    
    for(let i = 0; i < col; i++) { // 만든 dp배열의 1행을 문제에서 주어진 행렬의 1행으로 초기화
        dp[0][i] = land[0][i];
    }
    
    for(let i = 1; i < row; i++) { // 행 순회
        for(let j = 0; j < col; j++) { // 열 순회
            const rowArr = []; // 현재 행의 더한 값들 ex) 5 + 2, 5 + 3, 5 + 5를 저장할 배열인 rowArr
            
            for(let k = 0; k < col; k++) { // 현재 열만 제외하고 더하기 위한 순회 ex) 1열 제외 2, 3, 4열만 순회
                if(k !== j) rowArr.push(dp[i-1][k]); // N-1 행의 값들 저장 ( 현재 열 제외하고 )
            }
            
            dp[i][j] = Math.max(...rowArr) + land[i][j]; // 저장했던 N - 1행의 값들에서 최대값을 현재 N 행의 값과 더한다.
        }
    }
    
    return Math.max(...dp[row-1]); // N행에서 최댓값을 반환
}

다른 관점

나는 이 문제를 풀 때 dp라는 land와 동일한 크기의 배열을 새로 선언해서 이 dp에 칸들의 최댓값을 저장했었다.

그런데 이 land안에 있는 값을 나중에 다시 쓰는 것이 아니므로 사실 dp 배열을 새로 선언하지 않아도 되고 land배열에 덮어쓰며 최댓값을 저장해도 된다.

이 문제는 dp문제이고, dp문제를 풀 때 판단해야할 요소중 하나는 '주어진 자료를 다시 사용하느냐?' 이다. 만약 다시 사용한다고 하면 새로이 값을 저장할 자료형을 선언해야하고, 다시 사용하지 않는다면 주어진 자료에 덮어쓰기식으로 값을 저장하면 된다.

이는 공간복잡도에서 2배의 차이가 있으므로 유의미한 고려이다. 단순히 백준, 프로그래머스에서는 2배라는게 크게 중요하지 않지만, 실제로 업무에서 만약 1테라 데이터를 사용하고 있다면, 이를 처리하기 위해 1테라 짜리 저장용 배열을 새로 만드는 것은 매우 비효율 적인 작업이기 때문이다.

새로 알게된 것

dp에 대해서 처음 알게됐다.
dp는 빠른 속도를 요구하는 문제에 사용할 수 있다. (문제 힌트를 잘 읽어야겠다)
dp를 푼다는 것은 배열에 정보들을 저장해두었다가 사용하는 것이다.
결론적으론 dp는 메모리와 속도를 trade-off 한다.
주어진 배열의 이전 값이 다시 쓰이는지 확인한다.

설명에 오류가 있거나 이해가 어려운 부분이 있으면 댓글이나 이메일(pigkill40@naver.com)로 문의해 주시면 도움을 드리겠습니다.