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

땅따먹기

문제 설명

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(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 이하의 자연수

입출력 예

land	answer
[[1,2,3,5],[5,6,7,8],[4,3,2,1]]	16

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

코드

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

이 문제는 포기할까 100번은 넘게 생각했다. 도무지 모르겠어서 다른 사람의 풀이를 참고 해봤지만 아무리 봐도 모르겠고 자바스크립트로 푼 사람들도 적었다 😭 다른 언어의 풀이법도 보고 다양한 풀이법을 보면서 4시간을 내내 앉아있었다. 정말 이해가 하나도 안되고 내 머리를 탓하고 있다가 조금씩 코드를 쳐봤는데 갑자기 💡가 팍 켜지더니 정말 확 와닿았다.

 

"아..이제야 알겠네"

 

정말 이럴땐 무엇과도 비교할 수 없는 기쁨이 벅차오른다.

나같은 경우는 첫번째 행에서 최댓값을 구하고 해당 인덱스를 기억해서 다음 행의 같은 인덱스에 0을 할당해 다음 최댓값에서 제외하려고 했다. 하지만 잘못된 접근이었고 해결 방법은 다음과 같다.

1. answer에 빈 배열을 생성한다.
2. land의 행만큼 반복문을 돈다.
3. i(두 번째)행부터 i-1(위의)행의 본인 열(땅)을 제외한 나머지 열의 최댓값을 본인 열(땅)에 더하여 누적한다.
4. answer에 누적된 값들이 있는 마지막 행의 배열을 할당한다.
5. 마지막으로 누적된 값들의 최댓값을 반환한다.

의사코드 시각화

내 생각을 글로 설명하는 것도 능력인 것 같다 설명을 잘 못하는 것 같아서 그림으로 그려봤다.

결국에는 다이나믹 프로그래밍의 접근방법으로 풀어야 했다. 메모이제이션과 밑에서부터 계산하기의 사고 방식이 적용됐다. 앞으로 이런 유형의 문제들을 만나면 그래도 어느정돈 풀 수 있을 것 같다. 조금은 성장했다.