프로그래머스: 땅따먹기 (Dynamic Programming)

땅따먹기

총 N행 4열을 표현한 이중 배열이 주어질 때, 같은 열을 연속해서 선택하지 않고 한 칸만 선택하여 내려온다면 얻을 수 있는 가장 큰 점수를 구하기

제한 조건
1 ≤ N ≤ $10^5$ 인 자연수

문제 풀이 조건
열의 개수, 즉 각 배열의 길이는 4임.
각 배열의 요소는 점수를 표현함.
점수는 100 이하의 자연수임.

알고리즘 구상하기

시간복잡도를 줄이는데 집중한다.

문제를 해결하기 위해 순회해야 하는 배열의 길이는 최대 $10^5$에 달한다. 즉, 모든 배열을 이중 반복문으로 순회하는 것만으로 허용 가능한 반복 횟수인 $10^8$을 넘어간다.

반면 풀이를 구현하는 방법에만 집중하면 문제 자체는 어렵게 느껴지지 않았다.
반복 횟수라는 제한 조건을 고려하지 않는다면, 모든 선택의 경우의 수를 따져 점수를 계산하고 그중 가장 높은 점수를 채택하기만 하면 되기 때문이다.

이에 따라 시간복잡도를 우선적으로 고려하여, 배열을 순회하는 횟수를 최소화하는 데 상대적으로 더 집중하기로 했다.

적절한 알고리즘: 동적 프로그래밍(Dynamic Programming)

1차 시도: 재귀 함수

문제의 목적은 땅따먹기 최고점을 계산하는 것이다. 즉, 매 배열을 지날 때마다 이전에 선택한 index의 점수를 제외하고 가장 높은 점수를 선택하기만 하면 되는 것이다.

나는 처음에 위와 같이 문제를 해석한 후 ‘매 배열을 지날 때마다’라는 키워드에 집중했다.
땅(배열)만 다를 뿐, 같은 로직을 계속 수행하며 점수를 쌓는 점이 문제의 핵심이라 생각한 것이다.
이에 따라, 동일한 로직을 반복할 수 있는 재귀함수를 이용해 문제를 풀고자 했다.

그리고 다음과 같이 코드를 구현했다.

function solution(land) {
  const answer = [];
  const play = (prevIndex, stage, score) => {
    if (stage === land.length) {
      answer.push(score);
      return;
    }

    for (let i = 0; i <= land[0].length - 1; i += 1) {
      if (i !== prevIndex) {
        play(i, stage + 1, score + land[stage][i]);
      }
    }
  };

  play(-1, 0, 0);
  return Math.max(...answer);
}

코드 상으로는 땅을 표현한 이중 배열을 순회하며 이전 배열에서 선택한 index를 점수를 계산하는 함수에 전달했다.
그리고 함수가 해당 index를 제외한 배열 요소에서 점수를 더한 후, 자기 자신을 호출하여 동일한 로직을 반복하게 했다.
그러나 이는 눈에 보이는 반복문만 고려하고 재귀 함수가 처리되는 과정을 염두하지 않은 코드였다.

마치 잔가지를 뻗듯이 재귀함수가 각 가지마다 병렬적으로 실행될 것이라 생각하고 위와 같이 구현한 것이다.
그러나 실제로 재귀 함수는 중첩 호출되며, 실행 컨텍스트 스택에 저장되어 이전 호출이 모두 끝나야 다음 호출이 실행된다.

즉, 나는 재귀함수로 모든 경우의 수를 따져 이중 배열을 중첩 반복하고 있었던 것이다.
결국 1차로 구현한 코드는 런타임 에러를 얻었고, 이에 따라 새로운 로직을 구상하게 되었다.

2차 시도: 동적 프로그래밍(dp)

재귀 함수를 이용한 문제 풀이가 좌절되고 떠오른 것은 dp였다.

같은 로직을 반복해야 하는 점에 주목한 건 이전과 동일하지만, 이를 그대로 구현하는 대신 아예 반복 자체를 없애거나 최소화하는 방법에 초점을 두었다.

이전 땅(배열)에서 누적된 점수가 현재를 기준으로 얻을 수 있는 점수의 최댓값이라면, 이번 선택이 정답이 아니더라도 다시 처음부터 순회하며 계산할 필요가 없다는 점을 깨달은 것이다.

이에 따라, 이전에 누적한 점수를 저장하여 반복을 피하는 최적의 알고리즘인 dp를 선택하여 다시 구현했다.

문제 풀이 구상하기

우선 점수를 저장할 이중 배열을 선언했다. 그리고 깊이가 2인 배열의 요소에 각 index의 점수를 선택했을 경우, 누적되는 점수를 이 배열에 저장하도록 로직을 구현했다.

이 때, 현재의 index와 동일한 index를 제외하고 남은 경우의 수 3개를 고려하여 각각의 점수를 계산했다. 이 중 가장 큰 점수만 채택하여 dp의 현재 index의 값으로 저장하였다.

그 결과, 다음과 같은 코드가 완성되었다.

[JavaScript]

function solution(land) {
  const dp = Array.from({ length: land.length }, () =>
    Array.from({ length: 4 }, () => 0)
  );
  land.forEach((stage, stageIndex) => {
    if (stageIndex === 0) {
      dp[0] = stage;
    } else {
      stage.forEach((score, index) => {
        const totalScore = [];

        for (let i = 0; i <= 3; i += 1) {
          if (i !== index) {
            const scoreSum = dp[stageIndex - 1][i] + score;
            totalScore.push(scoreSum);
          }
        }

        const biggest = Math.max(...totalScore);
        dp[stageIndex][index] = biggest;
      });
    }
  });

  return Math.max(...dp.pop());
}