프로그래머스 #JavaScript - 땅따먹기

문제

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

풀이

1) 맞는 풀이 => 동적 프로그래밍의 활용 (해설 참고)

function solution(land) {
  var answer = 0;
  var len = land.length;
  
  for(var i =len-2; i>=0; i--){
    land[i][0] = Math.max(land[i+1][1], land[i+1][2], land[i+1][3])+land[i][0];
    land[i][1] = Math.max(land[i+1][0], land[i+1][2], land[i+1][3])+land[i][1];
    land[i][2] = Math.max(land[i+1][0], land[i+1][1], land[i+1][3])+land[i][2];
    land[i][3] = Math.max(land[i+1][0], land[i+1][1], land[i+1][2])+land[i][3];
 }
 answer = Math.max(...land[0]); /***포인트!!***/


    return answer;
}

2) 처음 틀린 풀이 => land[0]의 최대값에서 시작
문제점: 맨 처음 배열의 최대값을 구해서 시작하는 게 아니라 결과적으로 총합이 최대가 되어야 함.

function solution(land) {
  var answer = 0;
  var newIndex = 0;
  
   //첫 배열
   var index = land[0].indexOf(Math.max(...land[0]));
   var max = Math.max(...land[0]);

   answer = max;

    for(var i=1; i<land.length; i++){
         if(index !== land[i].indexOf(Math.max(...land[i]))){
         max = Math.max(...land[i]);
           index = land[i].indexOf(Math.max(...land[i]));
        answer = answer + max;
      }else{//같으면 그거 빼고 다음 큰거
        newIndex= land[i].indexOf(Math.max(...land[i]));
        land[i].splice(newIndex,1);
        index = newIndex;
        max = Math.max(...land[i]);
        answer = answer + max;
      }
    }

    return answer;
}

더 생각해보기

참고사항