생각을 넓히자

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

 

1. 열은 4개 고정
2. 행이 바뀔 수 있는 변수 한 칸만 밟으며 내려올 수 있음
3. 같은 행은 다음 열에서 밟지 못한다
4. 경우의 수 중 최대값 구하기

열은 4개 고정이니 행의 수만큼 반복하는건데 이 때 행의 수 안에서 열의 수만큼 반복문이 실행되야 한다 까지만 파악하고 나아가질 못했다 

 

그래서 다른 사람들이 푼 것을 해석해서 내 생각을 넓히려고 한다.

function solution(land) {
    let answer = 0;

    for (let i = 0; i < land.length; i++) {
        for (let j = 0; j < 4; j++) {
            if (i === 0) {
                continue;
            } else {
                let arr = land[i - 1].slice();
                arr[j] = 0; 
                land[i][j] += Math.max(...arr);
                // land[i][j] += Math.max.apply(null, arr); 이 부분은 스프레드 문법으로 교체 
                answer = Math.max(land[i][j], answer);
            }
        }
    }

    return answer;
}

문제의 핵심은 01, 12, 23 ... 이렇게 비교하며 최대값을 누적하는 것이다.

 

0번째 행이 시작될 땐 넘기고  1번째 행부터

• let arr = land[i - 1].slice();로 이전 0번째 행을 가져오고 
• 연속으로 밟지 못한다는 조건을 arr[j]=0으로 해결했다. 나는 어떻게 저 조건을 해결해야지 했는데 전혀 생각하지 못했다 
• land[i][j] += Math.max(...arr);를 통해 arr[j]=0 일 때 나머지 값 중 가장 큰 값을 더해서 1번째 행이 각 경우의 수 중에 가장 큰 값이 들어갔다 
• 2번째부터는 0과 1번째 행의 누적된 각 경우의 수가 1번째 행에 들어있기에 이걸 다시 2번째 행과 합쳐서 비교한다
• answer는 항상 최고 값을 유지한다 

 

이런 생각을 어떻게 했을까 진짜 나도 풀다보면 이렇게 생각을 할 수 있을까 싶다. 주기적으로 문제들을 다시 돌아봐야겠다.