[Programmers]땅따먹기/JS

문제링크

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

프로그래머스

---

접근방법

같은 열만 안밟으면 되는 문제인줄 알고 그렇게 풀었다가 테스트가 다 실패했다..

당황해서 문제 다시 정독해보니

얻을 수 있는 점수의 최대값을 return

알고보니 DP 문제였다.

문제를 보고 DP 문제인지 파악하는 것부터 어려운데.. ㅠㅅㅠ

DP로 푸니까 뚝딱 풀리는 문제였다!

 

처음코드

== 다 실패한 코드ㅋ

 

function solution(land) {
  var answer = 0;

  let prev = Math.max(land[0][0], land[0][1], land[0][2], land[0][3]);
  let prevIndex = land[0].indexOf(prev);
  answer += prev;

  for (let i = 1; i < land.length; i++) {
    let max = Math.max(land[i][0], land[i][1], land[i][2], land[i][3]);
    let maxIndex = land[i].indexOf(max);

    if (prevIndex == maxIndex) {
      land[i].splice(maxIndex, 1);
      max = Math.max(land[i][0], land[i][1], land[i][2]);
      maxIndex = land[i].indexOf(max);
    }
    answer += max;
  }
  return answer;
}

위의 방식으로 풀면 최대값을 return 할 수 없다.

그저 주어진 문제만 해결될뿐..ㅠ

[[1, 2, 3, 4],

[1, 2, 3, 100]]

위의 코드를 돌리면 4와 3을 선택하기 때문데 7이 return 된다.

문제에서는 최대값을 원하기 때문에 103이 return 되어야 정답이다.

정답코드

function solution(land) {
   var answer = 0;

    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])
    }
    let score=land[land.length-1]
    answer=Math.max(...score)
    
  return answer;
}

 

 

DP 방식으로 푸니까 해결됐따.

land[i][0]에는 land[i-1] 중 열이 0인 것을 제외하고 가장 큰 값을 더해서 저장

land[i][1]에는 land[i-1] 중 열이 1인 것을 제외하고 가장 큰 값을 더해서 저장

...

이렇게 4번 하면 land[land.length-1]에는 처음에 각 열을 선택했을 때 구할 수 있는 최대값들이 저장되어 있다.

이 중에서 가장 큰 값을 return 해주면 해결!