[프로그래머스] 땅따먹기 - 자바스크립트

문제

코딩테스트 연습 - 땅따먹기

 

풀이

처음에는 DFS로 접근했다.

 

N회까지 재귀를 돌면서, X행에서는 X-1행에서 선택하지 않은 열을 선택하여 더했다.
각각의 경우의 수로부터 N행까지 도달했을 때, 최댓값일 경우 최댓값을 갱신하도록 했다.

 

물론 주어진 행 N이 최대 100,000이기 때문에 재귀 호출로 인한 시간초과 이슈가 발생했다.

 

모든 경우의 수를 조회할 수 없다면, DP(동적 계획법)를 생각해봐야 한다.

 

풀이방법

 

DP답게 생각해보자.
land 행렬은 N x 4 크기이다.

 

각 행의 0,1,2,3 열에 도달하기까지 누적한 점수의 최댓값을 0,1,2,3열에 각각 저장해주자.

 

다음 작업을 1행부터 시작해서 N-1행까지 수행하면

0행부터 N-1행까지의 열 값은 각 행들의 열에 도달하기까지의 점수 최댓값이 기록된다.

 

코드로 보면 더 이해가 쉬울 듯 하다.

 

코드

function solution(land) {
  const N = land.length;

  for (let i = 1; i < N; i++) {
    for (let j = 0; j < 4; j++) {
      let max = Number.MIN_SAFE_INTEGER;
      for (let k = 0; k < 4; k++) {
        if (j === k) continue;
        max = Math.max(max, land[i - 1][k]);
      }
      land[i][j] += max;
    }
  }
  return Math.max(...land[N - 1]);
}

 

이와 같이 각 행에 있는 열 값에 열에 도달하기까지 최댓값을 기록해주면 빠르게 정답을 구할 수 있다.