[CodeKata] 프로그래머스 : 3.5(금), 땅따먹기

🥋 Ooooth!! (Level 2)

 

🧮 풀이

반복문이나 DFS를 시도했지만 마땅한 풀이가 나오지 않아, 프로젝트 진행을 위해 모범답안을 참고했다.

 

🖇 리뷰

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;
}

* 출처: velog.io/@sso/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-JavaScript-%EB%95%85%EB%94%B0%EB%A8%B9%EA%B8%B0

 

동적 프로그래밍을 활용한 방법이다! land 배열의 뒤에서부터 거슬러올라오면서 해당값을 바로 밑줄의 최대값과 더한 값으로 갱신한다.

코드도 간단하지만, 직관적이고 복잡하지 않은 그런 풀이인 것 같다. 동적 프로그래밍에 좀 더 익숙해져봐야겠다.