[프로그래머스 lev2/JS] 땅따먹기

문제 출처

프로그래머스 lev2 - 땅따먹기

나의 풀이

매우 단순하게 각 행의 최대값을 구하면 되는 거 아닌가? 라는 생각으로 접근했다.

1차시도(실패)

function solution(land) {
  let answer=0;
  let mIdx=-1;

  for (let i=0; i<land.length; i++) {
    let tmp = [];
    for (let j=0; j<4; j++) {
      if (j==mIdx) {
        tmp.push(-1);
      } else {
        tmp.push(land[i][j]);
      }
    }

    let max = Math.max.apply(null, tmp);
    mIdx = tmp.indexOf(max);
    answer += max;
  }
  return answer;
}

console.log(solution([
  [7, 2, 3, 5], 
  [5, 6, 7, 8], 
  [4, 3, 2, 1]]))

2차시도(실패/시간초과)

생각해보니, 어떤 요소를 선택하느냐에 따라 각 행에서의 최대값이 아니더라도 전체 최대값이 될 수 있겠다. 차라리 재귀로 전체 탐색하면서 풀어볼까.

재귀로 시간초과가 발생한다는 건 중복 탐색이 발생한다는 의미
=> 동적계획법/메모이제이션을 떠올려보자.

function solution(land) {
  let answer=0;
  
  function Eat(L, sum, idx) {
    if (L>=land.length) {
      // console.log(sum);
      answer = Math.max(answer, sum);
    }
    else {
      for (let i=0; i<4; i++) {
        if (i !== idx) {
          Eat(L+1, sum+land[L][i], i);
        }
      }
    }
  }
  Eat(0,0,-1);

  return answer;
}

console.log(solution([
  [1, 2, 3, 5], 
  [5, 6, 7, 8], 
  [4, 3, 2, 1]]))

다른 풀이 (통과코드)

// 동적계획법을 통한 풀이

행의 전진만 생각하지 말고, 뒷부분도 생각해보기

n번째 행의 최대값을 생각해보면,
n번째 행의 요소가 특정되는 순간, n-1번째 행의 최대값이 확정된다. 해당 요소 열을 제외한 나머지 중 최대값이므로.

이렇게 쭉쭉 순회하면 n-1번째 행의 최대값을 찾아서 n번째 행의 요소에 더해주면
=> 마지막 행에 각 요소에 각 요소에 따른 최대값이 남게 된다.

function solution(land) {
  for(let i=1; i<land.length; i++) {
      land[i][0] += Math.max(
          land[i-1][1],
          land[i-1][2],
          land[i-1][3],
      );
      land[i][1] += Math.max(
          land[i-1][0],
          land[i-1][2],
          land[i-1][3],
      );
      land[i][2] += Math.max(
          land[i-1][0],
          land[i-1][1],
          land[i-1][3],
      );
      land[i][3] += Math.max(
          land[i-1][0],
          land[i-1][1],
          land[i-1][2],
      );
  }
  
  return Math.max(...land[land.length-1]);
}

console.log(solution([
  [1, 2, 3, 5], 
  [5, 6, 7, 8], 
  [4, 3, 2, 1]]))