[DP] 프로그래머스 '땅따먹기' - js

1. 문제

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

프로그래머스

2. 코드

DP 즉 동적 계획법이란 특정 범위까지의 값을 구하기 위해 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이라고 한다. 어떤 문제를 해결하기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구했던 해를 활용하는 방식의 알고리즘이며 눈 앞에 보이는 최적의 해를 구하는 그리디와는 차이가 있다. 

정리해보자면 DP는 보장된 답을 구하기 위해 다른 범위까지 고려하여 답을 찾아나가는 알고리즘이다. 피보나치 문제에서 사용하는 메모이제이션도 DP에 해당하는 것 같다.

이 문제가 DP인 이유를 살펴보자. 만약 0번째 행에서 가장 큰 값인 4가 0번째 열에 있어 그 값을 첫 시작으로 고정하고 다음 행을 보려고 하는데 다음 행 0번째 열에 100이 있다면!? 0번째 행에서 0번째 열을 고정하여 선택한 것이 최선의 답은 아니다. 이렇기 때문에 첫번째 행에서 큰 값을 고정하여 시작하면 안된다. 뒤에 있는 다른 열의 상태도 봐가면서 최적의 답을 골라나가야 한다는 것이다.

이 문제의 핵심은 각 행의 값에 이전 행의 최댓값을 더해 나가는 방식을 사용하되, 이전 행의 최댓값이 있는 열이 지금 내가 보는 값의 열과 같다면 이전 행의 최댓값을 더하는게 아니라 차선책으로 이전 행의 두번째 큰 값을 더하고, 최종적으로 마지막 행에 있는 요소들의 최댓값을 반환하는 것이 정답이라는 것이다. 

function solution(land) {
  let answer = [];
  let len = land.length;
  for (let i = 1; i < len; 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]
    );
  }
  answer = land[land.length - 1];

  return Math.max(...answer);
}

 

이 문제와 DP에 대해 이해할 때 참고한 블로그)

https://shanepark.tistory.com/183

피보나치 수열과 프로그래머스 땅따먹기 문제로 알아보는 Dynamic Programming (동적 프로그래밍)

https://onlydev.tistory.com/71

[프로그래머스] 땅따먹기 | JavaScript

 

내 첫 DP 문제... 쉬운 알고리즘은 아닌 것 같다!

 

복기

6/3