땅따먹기

문제설명

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

처음 풀이 생각

처음에 시도했던 생각은 2차원 배열로 주어진 land의 원소, 즉 그 배열 안에서 제일 큰 수를 뽑고, 그 다음 배열에서는 index가 같은 값을 제외하고 뽑으면, 최대값을 구할 수 있다고 생각하고 문제를 풀었다.

처음 소스 코드

function solution(land) {
  var answer = 0;
  let before = 0;

  for (let i = 0; i < land.length; i++) {
    let max = 0;
    if (i === 0) {
      max = Math.max(...land[i]);
      before = land[i].findIndex(e => e === max);
      answer += max;
      continue;
    }
    let newArr = [...land[i]];
    newArr.splice(before, 1);
    max = Math.max(...newArr);
    before = land[i].findIndex(e => e === max);
    answer += max;
  }

  return answer;
}

하지만 이 방법으로 풀게 되면, [1,2,3,4] , [5,6,7,10] 같은 경우에 첫 배열에서 4를 고르고 그 다음은 7를 고르기 때문에 최댓값을 구할 수가 없다. 따라서 이 방법은 채점 결과 당연히 모두 틀렸었다.

그 후에 생각해낸 방법은 이전에 풀었던 정사각형 문제 풀이 방식에서 힌트를 얻고 해결했다.(동적프로그래밍 방법)

문제 풀이

[1,2,3,4](arr1) , [5,6,7,10](arr2)배열이 있을때, arr2[0]원소를 자신 인덱스 즉 0을 제외한 인덱스를 모두 더한 값들 중에 큰 값을 뽑아 arr2[0]에 할당한다.

5+1 = 6 => 같은 인덱스의 숫자는 선택할 수 없으므로 뺀다.
5+2 = 7
5+3 = 8
5+4 = 9

7,8,9 중에 제일 큰 값은 9 이므로 arr2 = [9,6,7,10]으로 바꾼다.

이 과정을 모든 인덱스에 대해서 실행하면, arr2 = [9,10,11,13]과 같이 나온다.

위의 과정을 주어진 land 배열 마지막 원소까지 실행하면 된다.

function solution(land) {
  var answer = 0;
  let before = 0;

  for (let i = 0; i < land.length - 1; i++) {
    land[i + 1] = max(land[i], land[i + 1]);
  }
  answer = Math.max(...land[land.length - 1]);
  return answer;
}

function max(arr1, arr2) {
  let stack = [];
  let newArr = [0, 0, 0, 0];
  for (let i = 0; i < arr2.length; i++) {
    for (let j = 0; j < arr1.length; j++) {
      if (j === i) continue;
      stack.push(arr1[j] + arr2[i]);
    }
    newArr[i] = Math.max(...stack);
    stack = [];
  }
  return newArr;
}

아쉬운 점 & 느낀 점

아쉬운 점은 아직 문제에 대해서 정확한 이해가 없이 푸는 것 같은게 너무 아쉽다. 너무 쉽게 생각한 것도 있고, 처음 시도 후에 동적 프로그래밍 방법으로 풀어야 겠다고 생각하기까지 너무 오랜 시간이 걸렸다. 문제를 많이 풀어보면 해결될 것이라고 믿지만 아쉬운 것은 어쩔 수가 없다. 그래도, 정사각형 문제를 푼 이후 동적 프로그래밍을 한번 접해서 그런가 구글링 없이 문제를 풀었기에 그래도 실력이 조금을 늘지 않았을까?라고 생각한다. 꾸준히 더 문제를 풀어야겠다.