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

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

프로그래머스

 

백준 9465번 스티커 문제와 상당히 유사하다

두 줄 짜리 스티커가 네 줄 짜리 땅으로 바뀌었을 뿐..

 

[💠 Class를 밀어보자/Class 4] - [BOJ][C++] 백준 9465번: 스티커

 

 

동적계획법(Dynamic Programming, DP)를 이용한다.

dp[i][j] 는 i행 j열까지 뛰었을 때 얻을 수 있는 최대 점수를 의미한다

 

바로 직전 줄에서 자신과 같은 열을 제외한 모든(3개) 열의 점수를 tmp 배열에 넣어서

그 tmp 배열에서 최댓값을 꺼내서 현재 위치와 더하면 현재 위치까지 얻을 수 있는 최대점수

 

function solution(land) {
    const row = land.length;
    let dp = land;
    for(let i=1; i<row; i++) {
        for(let j=0; j<4; j++) {
            let tmp = [];
            for(let k=0; k<4; k++) {
                if(k===j) {
                    continue;
                }
                tmp.push(land[i-1][k]);
            }
            dp[i][j] += Math.max(...tmp)
        }
    }
    return Math.max(...dp[row-1])
}