[DP] 땅따먹기

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

프로그래머스

 

 

의문점

한 열에 반복된 숫자는 없는지?

로직

1행에서 1칸만 선택한다

연속 같은 열은 선택할 수 없다

 

두번째 항부터 for을 돌린다.

전의 항의 가장 큰수, 그 수의 인덱스, 두번째 큰수를 구한다.

현재항마다 가장 큰수를 더하는데, 현재의 열이 그 전항 가장큰수의 열과 같을때는 두번쨰 큰수를 더한다.

이렇게 반복해서 마지막 항까지 내려온다

 

function solution(land) {
    for (let i = 1; i < land.length; i++) {
        const sortedLand = [...land[i-1]].sort((a, b) => b-a);
        const prevMax = sortedLand[0];
        const prevSecondMax = sortedLand[1]; 
        const prevMaxIndex = land[i-1].indexOf(prevMax);
        
        for (let j = 0; j < land[0].length; j++) {
            if (j !== prevMaxIndex) {
                land[i][j] += prevMax;
            } else {
                land[i][j] += prevSecondMax;
            }
        }
    } 
    console.log(land); // [ [ 1, 2, 3, 5 ], [ 10, 11, 12, 11 ], [ 16, 15, 13, 13 ] ]
    return land[land.length-1].sort((a, b) => b-a)[0];
}