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

아래 프로그래머스 로고를 클릭하면 해당 문제로 이동합니다 😀

풀이과정

---

요즘 문제 풀이가 바로 안떠오르는걸까 ... ?

처음 풀이는 Greedy하게 생각했다.
즉, 각 행마다 직전 열을 제외하고 가장 큰 값만 골라 누적을 했다.
그러나,,, 앞으로의 선택에 영향을 고려하지 않아서 모든 케이스에 대해 보장이 안되었다.

그래서 DP로 접근하면 어떨까 했다.
각 칸까지 올 수 있는 최대 점수를 누적해서 각 필드에 저장을 해버리는거다.
그리고 이게 정답이었다 ㅎㅅㅎ

코드

---

1. Python

def solution(land):
    N = len(land)
    for i in range(1, N):
        for j in range(4):
            land[i][j] += max(land[i - 1][k] for k in range(4) if k != j)
    return max(land[N-1])

2. JS

function solution(land) {
    const n = land.length;
    
    for(let i = 1 ; i < n ; i ++){
        for(let j = 0 ; j < 4 ; j++){
            land[i][j] += Math.max(...land[i-1].filter((_, idx) => idx !== j));
        }
    }
    
    return Math.max(...land[n-1]);
}

결과

---