[JS] 땅따먹기

동적계획법을 활용하여 풀 수 있는 문제였다.

 

 

쉽게 생각해서 4개짜리 배열을 하나 만들어서 각 단계별로 해당 발판을 밟았을때의 최대 점수를 기록하면 된다.

 

말로할때는 조금 이해가 안될 수 있는데 예시를 dp를 채워간 과정을 보면 꽤 쉽게 이해할 수 있다!

 

[ 1, 2, 3, 5 ] [ 10, 11, 12, 11 ] [ 16, 15, 13, 13 ]

 

 

1번 자리에 도착했다고 생각하면 그 전 단계에서 2,3,4번 자리에서 올 수 있는셈인데 2,3,4번 자리까지 누적된 점수의 가장 큰 값을 저장하면 된다.

 

 

 

 

function solution(land) {
    
    const dp = [0,0,0,0]
    
    for (const score of land){
        const tmp = [...dp]
        for (let i = 0 ; i < 4 ; i++) {
            dp[i] = Math.max(...tmp.filter((v,idx) => idx !== i)) + score[i]
        }
    }
    
    return Math.max(...dp)
}