[JS][프로그래머스LV2]땅따먹기

문제 번호

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

 

 

알고리즘 분류

 

 

문제 풀이

 오랜만에 DP 문제를 풀어보았다.

우선 문제에서 주어지는 land라는 2차원배열과 똑같은 모양의 2차원 DP 배열을 생성한다.

 let DP = land.map(x=>x.map(x=>x=0));

 

그리고 DP 배열의 첫번째 행은 문제에서 주어진 land 와 같은 내용으로 채웠다.

for(let i=0; i<DP[0].length; i++){
    DP[0][i] = land[0][i];
}

 

past 변수는 이전 행의 가장 큰 수가 위치하는 열을 나타낸다.

max 변수는 행의 가장 큰 수를 나타낸다.

let past = DP[0].indexOf(Math.max(...DP[0]));
let max = Math.max(...DP[0]);

 

이제 2차원 DP 배열을 채워야한다.

DP배열의 각 칸은 land배열을 i행 까지 탐색하였을때 가질 수 있는 최대값을 보관하게 된다.

(좀 더 자세한 설명은 아래의 블로그에 있다.)

피보나치 수열과 프로그래머스 땅따먹기 문제로 알아보는 Dynamic Programming (동적 프로그래밍)

for(let i=1; i<DP.length; i++){
        for(let j=0; j<4; j++){
            if( j !== past){
                DP[i][j] = land[i][j] + max;
            }
            else if(j === past){
                DP[i][j] = land[i][j] + DP[i-1].slice(0).sort((a,b)=>b-a)[1];
            }            
        }    
        past = DP[i].indexOf(Math.max(...DP[i]));
        max = Math.max(...DP[i]);
    }

* splice 와 slice 를 헷깔리지 않도록 주의하자 *

 

이후 past 와 max 를 갱신하면서 DP배열을 모두 채워주면 된다.

그리고 DP배열의 마지막 행에서 최대값을 찾아서 반환해주면 된다.

 

전체코드

function solution(land) {        
    let DP = land.map(x=>x.map(x=>x=0));
    for(let i=0; i<DP[0].length; i++){
        DP[0][i] = land[0][i];
    }    
    
    let past = DP[0].indexOf(Math.max(...DP[0]));
    let max = Math.max(...DP[0]);
    //console.log(DP)
    for(let i=1; i<DP.length; i++){
        for(let j=0; j<4; j++){
            if( j !== past){
                DP[i][j] = land[i][j] + max;
            }
            else if(j === past){
                DP[i][j] = land[i][j] + DP[i-1].slice(0).sort((a,b)=>b-a)[1];
            }            
        }    
        past = DP[i].indexOf(Math.max(...DP[i]));
        max = Math.max(...DP[i]);
    }
    console.log(DP);
    
    return Math.max(...DP[land.length-1]);
}

특이사항