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

🗒️ 문제

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

⚠ 제한사항

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

📝 문제 해설

시간이 매우 오래 걸린 문제 중 하나이다. 첫번째로 코드를 짰을 때에는 짧은 줄에 가능했는데 테스트 케이스는 통과했지만 전체 실패가 떴다. 그 이유는 바로 해당 열이 그 전 행의 최댓값인 행인 경우에 피할 수 있었지만 그것이 곧 최대값을 의미하는 것이 아니었기 때문이다.

따라서 다른 방법을 찾아봤어야 했는데, 다른 사람들의 풀이는 DP 풀이가 많았다. 뭔가 직관적으로 이해가 가지 않아서 다른 방법을 고수하다 찾은 방법이 바로 아래와 같은 풀이다. 우선 모든 행에 있는 값을 다음 행에 누적해서 계산하는 것이다. 하지만 해당 행의 인덱스에서는 그 전에 같은 인덱스를 제외하고 나머지 배열에 있는 값중에 최대값을 넣어서 계산한다. 이렇게 계산하면 순차적으로 누적하여 계산한 배열이 존재하고 land 배열 가장 끝에 최종배열이 존재하게 된다. 그 배열을 새로운 배열 arr에 복사하고 거기서 최대값을 리턴해주면 해결이 되는 문제이다.

💡 필요 문법

Math.max()

Math.max(array)를 입력하면 array 중에서 가장 큰 값을 리턴한다.

💻 코드

function solution(land) {
  let arr = [];

  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]
    );
  }
  arr = land[land.length - 1]; // land 배열은 이중배열이다. 가장 끝에 있는 배열이 누적 값이므로 가장 끝 배열을 arr 배열에 복사한다

  return Math.max(...arr); // arr에서 가장 큰 값을 반환한다
}