🔎 땅따먹기

❓ 문제링크

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

📄 제출 코드

function solution(land) {
  let answer = 0;
  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 = Math.max(...land[len-1]);
  return answer;
}
// let land = [[1, 2, 3, 5], [5, 6, 7, 8], [4, 3, 2, 1]];
let land = [[4, 3, 2, 1], [2, 2, 2, 1], [6, 6, 6, 4], [8, 7, 6, 5]];
console.log(solution(land));

처음에 생각한 방법은 줄마다 max값을 구해서 그 max의 idx를 찾고, 이전 idx와 비교하고 같으면 그 max값을 -1로 바꾸고, 그 다음 max를 구하여 해당 값을 더해 나갔다.
그러나 전부 실패가 떠서 뭐지? 했었다.
let land = [[4, 3, 2, 1], [2, 2, 2, 1], [6, 6, 6, 4], [8, 7, 6, 5]];이 경우가 반례인데 4 2 6 8로 0번째, 1번째, 3번째를 하면 8을 고를 수 있다.
하지만, 내가한 방식대로 풀면 0번째, 1번째, 0번째를 골라서 8을 못고르고 7을 고르게 되어 틀리게된다.

그러면 어떻게 풀어야할까 고민하다가 결국 풀지 못하고, 풀이 영상을 봤다.
풀이는 다음과 같다.
배열이 있으면 아래로 내려가면서 이전꺼의 나머지 idx값을 더해서 각각 최대값이 되는 경우를 현재 위치에 저장한다. 그렇게 마지막까지 다 더하고나면, 마지막열에서 최대값을 골랐을 때 제일 큰 수를 구할 수 있다.

❗주의 문제를 잘 읽자!!
영상풀이가 왜 4개경우만 생각하지라고 생각하고 이해가 안가다가 문제를 다시보니 N이 4까지 인 걸 알았다,,😅

📘 참고

https://programmers.co.kr/learn/courses/18/lessons/846