(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

---

solution.js

function solution(land) {
    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]);
    }
    return Math.max(...land[land.length - 1]);
}

 

문제 이해를 돕기 위한 그림과 설명

i = 행, j = 열

i = 1 ( 2행 ) 부터 시작하는 이유는 1행의 값은 변하지 않고 고정이기 때문입니다.

먼저 2행의 값을 구하기 위해, 1행에서 가장 큰 수인 5와 1행과 연속되지 않는 2행 열들의 값들을 더합니다.

1행의 5는 4열 , 2행의 8은 4열로 서로 같은 열이기 때문에 1행에서 5다음으로 큰 수 3과 8을 더합니다.

 

그 다음 3행의 값을 구하기 위해, 2행에서 가장 큰수인 12와 2행과 연속되지 않는 3행 열들의 값들을 더합니다.

2행의 12는 3행의 2의 값과 같은 열이므로 12 다음으로 큰 수인 11과 2를 더합니다.

 

이 과정들로 인해 마지막으로 얻을 수 있는 배열은 다음과 같으며 여기서 제일 큰 수 ( max ) 16이 결과값입니다.

1	2	3	5
10	11	12	11
16	15	13	13

 

코드 해설

1. for 구문을 통해 각 행과 열에서 가장 큰 수를 land[][] 배열에 추가합니다.

2. 이 예시에서 여기서 land의 배열은 다음과 같습니다. 

1	2	3	5
5	6	7	8
4	3	2	1

3. 1행 1열 ~ 1행 4열 ( i = 0 , j = 0 ) ~ ( i = 0, j = 3) 에서 가장 큰 수는 5 이며  land[1][0]에 더합니다.
       => 2열 ( j = 1 ) 부터 시작한 이유는 land[1][0] 이 1열이므로 겹치기 때문입니다.

 

4. land[1][0]에 5를 더하게 되면 land의 배열은 다음과 같아집니다. ( 기존 5에 5를 더해 10이 되었습니다. )

1	2	3	5
10	6	7	8
4	3	2	1

5. 이와 같은 방법으로 2행 1열 ~ 2행 4열 까지 열이 중복되지않은 1행의 큰 수를 더합니다.

1	2	3	5
10 ( 5 + 5 )	11 ( 6 + 5 )	12 ( 7 + 5 )	11 ( 8 + 3 )
4	3	2	1

 6. 2행과 똑같이 3행을 구하면 다음과 같습니다.

1	2	3	5
10	11	12	11
16 ( 12 + 4 )	15 ( 12 + 3 )	13 ( 11 + 2 )	13 ( 12 + 1 )

7. 마지막으로, Math.max(...land[land.length - 1]) 최종으로 합해진 수들이 3행에 있기 때문에 i = 2 ( 3행 ) 중 max 값을 찾습니다.

 

8. 결과는 다음과 같이 출력됩니다.

console.log(solution([[1,2,3,5],[5,6,7,8],[4,3,2,1]])); // --> 16