(프로그래머스 JS)땅따먹기

https://programmers.co.kr/learn/courses/30/lessons/12913

코딩테스트 연습 - 땅따먹기

 

DP 알고리즘 사용.

land[i][j] 에 있는 값과 land[i - 1][k]에 있는 값을 더해서 가장 큰 점수만 answer에 저장한다. 단, j != k.

 

알기 쉽게 예제에 있는 land를 사용해서 설명하겠다.

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

1행이 아닌 2행부터 시작하여 가장 큰 값을 answer 배열에 저장한다.

그렇기 위해서 answer의 1행은 land의 1행으로 채워놓은 후 시작한다.

1	2	3	5
0	0	0	0

for문을 이용해 answer 배열의 빨간 0 열 위치에서 가장 가장 큰 값을 찾아 저장하면 된다.

빨간 0의 인덱스를 answer[i][j]라고 했을 때,

answer[i][j] = max(현재 answer[i][j] 값, land[i][j] + land[i - 1][k]) 로 나타낼 수 있다.

(1 + 5) , (2 + 5), (3 + 5), (5 + 5)가 빨간 0의 위치에서 수행하는 덧셈이다.

하지만 문제에서 연속된 열의 위치를 밟을 수 없기 때문에 (1 + 5)는 수행하지 않는다.

그렇다면 결과는 아래와 같이 되며, 다음 열의 위치로 이동하게 된다.

1	2	3	5
10	0	0	0

이와 같은 방식으로 2행을 채우게 되면

1	2	3	5
10	11	12	11

이렇게 테이블을 나타낼 수 있다.

 

마지막 3행을 채우기 위해서는 2행에 저장된 값을 사용하여 같은 방식으로 채우면 된다.

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

모든 for문을 돌게 되면 위와 같은 결과를 얻게 되고,

가장 마지막 행에서 큰 값을 구하면 된다.

function solution(land) {
    const answer = [[...land[0]]];
    const N = land.length;
    
    for(let i = 1; i < N; i++){
        answer.push([0, 0, 0, 0]);
        
        for(let j = 0; j < 4; j++){
            for(let k = 0; k < 4; k++){
                if(j !== k){
                    answer[i][j] = answer[i][j] < land[i][j] + answer[i - 1][k] ? land[i][j] + answer[i - 1][k] : answer[i][j];
                }
            }
        }
    }

    return Math.max(...answer[N - 1]);
}