📝 땅따먹기

🖥 나의 JS 코드

처음에는 첫번째 열에서 최대값을 구하고, 해당 인덱스를 찾아서 다음 열에서는 이를 제외한 곳에서의 최대값을 찾아 더해나가는 방식으로 구현하였다

function solution(land) {
    var answer = 0;

    let index = -1;
    land.map((data)=>{
        let max = Math.max(...data);
        if(data.indexOf(max) != index){
            answer += max;
            index = data.indexOf(max) ;
        } else {
            data[index] = 0;
            max = Math.max(...data);
            answer += max;
            index = data.indexOf(max);
        }
        
    })
    return answer;
 
}

👇 테스트 코드 첫번째는 가볍게 통과하였지만

입력 : [[1,2,3,5],[5,6,7,8],[4,3,2,1]]
결과 : 16
기댓값 : 16

👇 테스트 코드 두번째는 통과하지 못하였다.

입력 : [[1, 2, 3, 5], [5, 6, 7, 100], [4, 3, 2, 1]]
결과 : 16
기댓값 : 107

이에 대한 분석을 해보았다.
처음 최대값은 5이지만 다음 최대값인 100은 5와 같은 인덱스에 있으므로 이를 더하지 못해 7를 대신 더하게 된다. 하지만, 이는 올바른 계산값이 아니다! 100을 더해주어야 마지막 행까지 내려왔을 때, 얻을 수 있는 점수의 최대값이 나오게 된다.

이를 해결하기 위해서 나는 각 행의 최대값을 다음 행에 더해주는 논리 를 사용하였다.

테스트 코드 두번째의 예시를 살펴보면,
[5, 6, 7, 100] 각각에 대해 5 ,5 , 5, 3을 더하여 [10, 11, 12, 103]으로 만들어준다.
이후 세번째 행 [ 4, 3, 2, 1 ] 각각에 대해 103, 103, 103, 12를 더해주면 [ 107, 106, 105, 13]이 나오므로 마지막 행에서의 최대값을 반환하면 문제를 해결하게 된다.

최종 코드는 다음과 같다👇

function solution(land) {
    var answer = 0;

  // 우선 첫번째 행의 최대값과 인덱스를 구하고
    let max = Math.max(...land[0]);
    let index = land[0].indexOf(max);
    
  // 반복문은 두번째 행부터 끝까지 실행한다
    for(let i = 1; i < land.length ; i++){
      // 열을 4로 고정되어 있다
        for(let j = 0 ; j < 4; j++){
          // 최대값의 인덱스와 다르면,
         // 최대값을 더하면 된다
            if(j != index){
                land[i][j] += max;
            }else{
              // 인덱스가 같으면
              // 최대값 다음의 값을 더해주어야 하므로
              // 배열을 복사한뒤 그 값을 가져온다
                const next = [...land[i-1]];
                next[index] = 0;
                land[i][j] += Math.max(...next);
            }
        }
      // 반복문이 끝나면, 해당 행에서 다시 최대값을 구하고
      // 그 위치를 가져온다
          max = Math.max(...land[i]);
        index = land[i].indexOf(max);
    
    }
  // 마지막 행에서의 최대값을 반환하면 끝
    return Math.max(...land[land.length-1]);
}