[Programmers] 땅따먹기

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

프로그래머스

def solution(land):
    answer = 0
    
    for i in range(1, len(land)):
        land[i][0] += max(land[i-1][1], land[i-1][2], land[i-1][3])
        land[i][1] += max(land[i-1][0], land[i-1][2], land[i-1][3])
        land[i][2] += max(land[i-1][0], land[i-1][1], land[i-1][3])
        land[i][3] += max(land[i-1][0], land[i-1][1], land[i-1][2])
    answer = max(land[-1])
    return answer

맨 처음엔 그리디 방식으로 풀려했는데 전부 틀려서 왜지 하고 생각해 보았는데 같은 숫자가 있을 경우를 생각 못했다.

따라서 DP 동정 계획법으로 풀어야 한다.

가장 높은 값을 저장하면서 내려오면 마지막 행에서 가장 큰 값이 경우의 수 중 가장 큰 값이다.

​

(참고 블로그 : https://shanepark.tistory.com/183)